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

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


 

For example,


Input: 

[ 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 ]
[ 1  1  1  1  0  0  0  1  0  1 ]
[ 1  1  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 ]

Output: 

[ 1  1  1  1  1  1  1  1  1  1 ]
[ 1  0  0  1  1  1  1  1  1  1 ]
[ 1  0  0  1  1  1  1  1  1  1 ]
[ 1  1  1  1  0  0  1  1  1  1 ]
[ 1  1  1  1  0  0  0  1  1  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  0  0  1  0  1 ]
[ 1  1  1  1  1  0  1  0  0  1 ]
[ 1  1  1  1  1  1  1  1  1  1 ]

 

 
We can use DFS 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 to replace all connected 0’s. Note that we don’t need a visited array here as we are replacing the value of every processed node and it won’t be considered again next time as it will have value 1.

C++

Download   Run Code

Output:

1  1  1  1  1  1  1  1  1  1
1  0  0  1  1  1  1  1  1  1
1  0  0  1  1  1  1  1  1  1
1  1  1  1  0  0  1  1  1  1
1  1  1  1  0  0  0  1  1  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  0  0  1  0  1
1  1  1  1  1  0  1  0  0  1
1  1  1  1  1  1  1  1  1  1

Java

Download   Run Code

Output:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 1, 1, 1, 1]
[1, 1, 1, 1, 0, 0, 0, 1, 1, 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, 0, 0, 1, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

 
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  
newest oldest most voted
Notify of
P G
Guest

Nice logic and clean code!!