# 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)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂