# 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]

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 🙂

Get great deals at Amazon