Change all elements of row i and column j in a matrix to 0 if cell (i, j) has value 0

Give a M x N matrix consisting of only 0 or 1, change all elements of row i and column j to 0 if cell (i, j) has value 0. Do this without using any extra space for every (i, j) having value 0.


For example,


Input:
[ 1 1 0 1 1 ]
[ 1 1 1 1 1 ]
[ 1 1 1 0 1 ]
[ 1 1 1 1 1 ]
[ 0 1 1 1 1 ]

Output:
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]
[ 0 1 0 0 1 ]
[ 0 0 0 0 0 ]

Explanation: 0’s are present at (0, 2), (4, 0) and (2, 3) in input matrix. So

  • we change all elements of row 0 and column 2 to 0
  • we change all elements of row 4 and column 0 to 0
  • we change all elements of row 2 and column 3 to 0


 


 
A simple solution would be to traverse the matrix and if we encounter any cell (i, j) that has value 0, change each element in row i and column j to some arbiray value other than 0 or 1. Later traverse the matrix once again and replace all elements with assigned value to 0.

C++

Download   Run Code

Output:

0 0 0 0 0
0 1 0 1 1
0 0 0 0 0
0 1 0 1 1
0 0 0 0 0

Above solution has time complexity of O(M*N*(M+N)) which is not efficient.

We can solve this problem in O(M*N) time as well. The idea is to traverse the matrix once and use first row & first column (or last row & last column, ..) to mark if any cell in corresponding row or column has value 0 or not. Before doing that, we initially mark if the chosen row/column have any 0’s present in them in two separate flags.

Note that this method will work for any integer matrix (not just binary matrix).

C++

Download   Run Code

Output:

0 0 0 0 0
0 1 0 0 7
0 0 0 0 0
0 4 0 0 9
0 0 0 0 0

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Lucas Daniel
Guest
Lucas Daniel

The first solution is incorrect it will fail for:
{ 1, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1 }

wpDiscuz