Replace all occurrences of 0 that are surrounded by 1 in a binary matrix

Given an M × N binary matrix, replace all occurrences of 0’s by 1’s, which are completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).

For example, consider the following matrix:

[  1  1  1  1  0  0  1  1  0  1  ]
[  1  0  0  1  1  0  1  1  1  1  ]
[  1  0  0  1  1  1  1  1  1  1  ]
[  1  1  1  1  0  0  1  1  0  1  ]
[  0  0  1  1  0  0  0  1  0  1  ]
[  1  0  0  1  1  0  1  1  0  0  ]
[  1  1  0  1  1  1  1  1  1  1  ]
[  1  1  0  1  1  0  0  1  0  1  ]
[  1  1  1  0  1  0  1  0  0  1  ]
[  1  1  1  0  1  1  1  1  1  1  ]

The solution should convert it into the following matrix:

[  1  1  1  1  0  0  1  1  0  1 ]
[  1  1  1  1  1  0  1  1  1  1 ]
[  1  1  1  1  1  1  1  1  1  1 ]
[  1  1  1  1  1  1  1  1  0  1 ]
[  0  0  1  1  1  1  1  1  0  1 ]
[  1  0  0  1  1  1  1  1  0  0 ]
[  1  1  0  1  1  1  1  1  1  1 ]
[  1  1  0  1  1  1  1  1  1  1 ]
[  1  1  1  0  1  1  1  1  1  1 ]
[  1  1  1  0  1  1  1  1  1  1 ]

Practice this problem

We can use the flood fill algorithm to solve this problem. The idea is to consider all zeros present on the matrix’s boundary one by one and start a Depth–first search (DFS) from them. The DFS procedure replaces all such connected zeros by value -1.

After processing all connected zeros present on the matrix boundary, traverse the matrix again, replace all remaining zeros with 1 and replace all -1 already present in the matrix back to zero.

The algorithm can be implemented as follows in C++, Java, and Python:

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

// Below arrays detail all eight possible movements

int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

// The function returns true if it is possible to go to cell `(x, y)`.

// It returns false when the cell is invalid or is different from the target

bool isSafe(vector<vector<int>> &mat, int x, int y, int target)

{

int M = mat.size();

int N = mat[0].size();

return (x >= 0 && x < M && y >= 0 && y < N) &&

mat[x][y] == target;

}

// Flood fill using DFS

void floodfill(vector<vector<int>> &mat, int x, int y, int replacement)

{

int M = mat.size();

int N = mat[0].size();

// get the target value

int target = mat[x][y];

// replace current cell value with that of replacement

mat[x][y] = replacement;

// process all eight adjacent cells of the current cell and

// recur for each valid cell

for (int k = 0; k < 8; k++)

{

// if the adjacent cell at position `(x + row[k], y + col[k])` is

// valid and has the same value as that of the current cell

if (isSafe(mat, x + row[k], y + col[k], target)) {

floodfill(mat, x + row[k], y + col[k], replacement);

}

// Replace all occurrences of 0 by 1, which are surrounded

// by 1 in a binary matrix

void replaceZeros(vector<vector<int>> &mat)

{

// base case

if (mat.size() == 0) {

return;

}

// `M × N` matrix

int M = mat.size();

int N = mat[0].size();

// visit all cells in the first and last row of the matrix

for (int i = 0; i < N; i++)

{

if (mat[0][i] == 0) {

floodfill(mat, 0, i, -1);

}

if (mat[M - 1][i] == 0) {

floodfill(mat, M - 1, i, -1);

}

// visit all cells in the first and last column of the matrix

for (int i = 0; i < M; i++)

{

if (mat[i][0] == 0) {

floodfill(mat, i, 0, -1);

}

if (mat[i][N - 1] == 0) {

floodfill(mat, i, N - 1, -1);

}

// traverse the given matrix

for (int i = 0; i < M; i++)

{

for (int j = 0; j < N; j++)

{

// replace every 0 with 1

if (mat[i][j] == 0) {

mat[i][j] = 1;

}

// replace every -1 with 0

if (mat[i][j] == -1) {

mat[i][j] = 0;

}

// Function to print the matrix

void printMatrix(vector<vector<int>> const &mat)

{

for (auto &row: mat) {

for (auto &i: row) {

cout << setw(3) << i;

}

cout << endl;

}

cout << endl;

}

int main()

{

vector<vector<int>> mat =

{

{ 1, 1, 1, 1, 0, 0, 1, 1, 0, 1 },

{ 1, 0, 0, 1, 1, 0, 1, 1, 1, 1 },

{ 1, 0, 0, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 0, 0, 1, 1, 0, 1 },

{ 0, 0, 1, 1, 0, 0, 0, 1, 0, 1 },

{ 1, 0, 0, 1, 1, 0, 1, 1, 0, 0 },

{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 0, 1, 1, 0, 0, 1, 0, 1 },

{ 1, 1, 1, 0, 1, 0, 1, 0, 0, 1 },

{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }

};

replaceZeros(mat);

printMatrix(mat);

return 0;

}

Download Run Code

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

import java.util.Arrays;

class Main

{

// Below arrays detail all eight possible movements

private static final int[] row = {-1, -1, -1, 0, 0, 1, 1, 1};

private static final int[] col = {-1, 0, 1, -1, 1, -1, 0, 1};

// The function returns true if it is possible to go to cell `(x, y)`

// It returns false when the cell is invalid or is different from the target

private static boolean isSafe(int[][] mat, int x, int y, int target)

{

int M = mat.length;

int N = mat[0].length;

return (x >= 0 && x < M && y >= 0 && y < N) &&

mat[x][y] == target;

}

// Flood fill using DFS

private static void floodfill(int[][] mat, int x, int y, int replacement)

{

// get the target value

int target = mat[x][y];

// replace current cell value with that of replacement

mat[x][y] = replacement;

// process all eight adjacent cells of the current cell and

// recur for each valid cell

for (int k = 0; k < 8; k++)

{

// if the adjacent cell at position `(x + row[k], y + col[k])` is

// valid and has the same value as that of the current cell

if (isSafe(mat, x + row[k], y + col[k], target)) {

floodfill(mat, x + row[k], y + col[k], replacement);

}

// Replace all occurrences of 0 by 1, which are surrounded

// by 1 in a binary matrix

public static void replaceZeros(int[][] mat)

{

// base case

if (mat == null || mat.length == 0) {

return;

}

// `M × N` matrix

int M = mat.length;

int N = mat[0].length;

// visit all cells in the first and last row of the matrix

for (int i = 0; i < N; i++)

{

if (mat[0][i] == 0) {

floodfill(mat, 0, i, -1);

}

if (mat[M - 1][i] == 0) {

floodfill(mat, M - 1, i, -1);

}

// visit all cells in the first and last column of the matrix

for (int i = 0; i < M; i++)

{

if (mat[i][0] == 0) {

floodfill(mat, i, 0, -1);

}

if (mat[i][N - 1] == 0) {

floodfill(mat, i, N - 1, -1);

}

// traverse the given matrix

for (int i = 0; i < M; i++)

{

for (int j = 0; j < N; j++)

{

// replace every 0 with 1

if (mat[i][j] == 0) {

mat[i][j] = 1;

}

// replace every -1 with 0

if (mat[i][j] == -1) {

mat[i][j] = 0;

}

public static void main(String[] args)

{

int[][] mat =

{

{ 1, 1, 1, 1, 0, 0, 1, 1, 0, 1 },

{ 1, 0, 0, 1, 1, 0, 1, 1, 1, 1 },

{ 1, 0, 0, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 1, 1, 0, 0, 1, 1, 0, 1 },

{ 0, 0, 1, 1, 0, 0, 0, 1, 0, 1 },

{ 1, 0, 0, 1, 1, 0, 1, 1, 0, 0 },

{ 1, 1, 0, 1, 1, 1, 1, 1, 1, 1 },

{ 1, 1, 0, 1, 1, 0, 0, 1, 0, 1 },

{ 1, 1, 1, 0, 1, 0, 1, 0, 0, 1 },

{ 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }

};

replaceZeros(mat);

for (var r: mat) {

System.out.println(Arrays.toString(r));

}

Download Run Code

Python

# Below lists detail all eight possible movements

row = [-1, -1, -1, 0, 0, 1, 1, 1]

col = [-1, 0, 1, -1, 1, -1, 0, 1]

# The function returns true if it is possible to go to cell `(x, y)`

# It returns false when the cell is invalid or is different from the target

def isSafe(mat, x, y, target):

return (0 <= x < len(mat) and 0 <= y < len(mat[0])) and mat[x][y] == target

# Flood fill using DFS

def floodfill(mat, x, y, replacement):

# get the target value

target = mat[x][y]

# replace current cell value with that of replacement

mat[x][y] = replacement

# process all eight adjacent cells of the current cell and

# recur for each valid cell

for k in range(8):

# if the adjacent cell at position `(x + row[k], y + col[k])` is

# valid and has the same value as that of the current cell

if isSafe(mat, x + row[k], y + col[k], target):

floodfill(mat, x + row[k], y + col[k], replacement)

# Replace all occurrences of 0 by 1, which are surrounded

# by 1 in a binary matrix

def replaceZeros(mat):

# base case

if not mat or not len(mat):

return

# `M × N` matrix

(M, N) = (len(mat), len(mat[0]))

# visit all cells in the first and last row of the matrix

for i in range(N):

if mat[0][i] == 0:

floodfill(mat, 0, i, -1)

if mat[M - 1][i] == 0:

floodfill(mat, M - 1, i, -1)

# visit all cells in the first and last column of the matrix

for i in range(M):

if mat[i][0] == 0:

floodfill(mat, i, 0, -1)

if mat[i][N - 1] == 0:

floodfill(mat, i, N - 1, -1)

# traverse the given matrix

for i in range(M):

for j in range(N):

# replace every 0 with 1

if mat[i][j] == 0:

mat[i][j] = 1

# replace every -1 with 0

if mat[i][j] == -1:

mat[i][j] = 0

if __name__ == '__main__':

mat = [

[1, 1, 1, 1, 0, 0, 1, 1, 0, 1],

[1, 0, 0, 1, 1, 0, 1, 1, 1, 1],

[1, 0, 0, 1, 1, 1, 1, 1, 1, 1],

[1, 1, 1, 1, 0, 0, 1, 1, 0, 1],

[0, 0, 1, 1, 0, 0, 0, 1, 0, 1],

[1, 0, 0, 1, 1, 0, 1, 1, 0, 0],

[1, 1, 0, 1, 1, 1, 1, 1, 1, 1],

[1, 1, 0, 1, 1, 0, 0, 1, 0, 1],

[1, 1, 1, 0, 1, 0, 1, 0, 0, 1],

[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

]

replaceZeros(mat)

# print matrix

for r in mat:

print(r)

Download Run Code

Output:

[1, 1, 1, 1, 0, 0, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 0, 0, 1, 1, 1, 1, 1, 0, 0]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 0, 1, 1, 1, 1, 1, 1]

The time complexity of the proposed solution is O(M × N) for an M × N matrix. The auxiliary space required by the program is O(M × N) for recursion (call stack).