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

Give a M x N binary matrix, replace all occurrences of 0 by 1 which are completely surrounded by 1.

For example, consider below matrix:

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

It should be converted to below matrix:

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

We can use flood fill algorithm to solve this problem. The idea is to consider all zeroes present on the boundary of the matrix one by one and start a depth first search from them. The DFS procedure replace all such connected zeroes by value -1.

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

The time complexity of above solution is O(M * N).

(1 votes, average: 5.00 out of 5)