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.

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

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).

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

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 votes, average: 5.00 out of 5)

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 🙂