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.

 

Download   Run Code

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of