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

Java

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

Java

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]

 
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
Lucas Daniel
Guest

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 }