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++ implementation –
 

Download   Run Code

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

 
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++ implementation –
 

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
wpDiscuz