Set Matrix Zeros

Easy
0/40
Average time to solve is 30m
1417 upvotes
Asked in companies
GoogleAmazonDunzo

Problem statement

You are given an N x M integer matrix. Your task is to modify this matrix in place so that if any cell contains the value 0, then all cells in the same row and column as that cell should also be set to 0.

Requirements:

  • If a cell in the matrix has the value 0, set all other cells in that cell's row and column to 0.
  • You should perform this modification in place (without using additional matrices).

You must do it in place.

For Example:

If the given grid is this:
[7, 19, 3]
[4, 21, 0]

Then the modified grid will be:
[7, 19, 0]
[0, 0,  0]
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the no. of the rows and columns of the matrix.

The next 'N' lines will contain ‘M’ space separated integers representing the elements of the matrix.

Output Format:

For each test case, print the modified grid.

Print output of each test case in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ m, n ≤ 1000
Σ(m * n) ≤ 2000000
-2^(31) ≤ matrix[i][j] ≤ 2^(31)-1, for all (1 ≤ i ≤ n and 1 ≤ j ≤ m).

Time Limit: 1 sec

Follow up:

Can we do better than O(m * n) space?
Using O(m + n) space is an improvement but we can still do better.
We can do it using constant memory. Can you do it?
Sample Input 1 :
2
2 3
7 19 3
4 21 0
3 3
1 2 3
4 0 6
7 8 9
Sample Output 1 :
7 19 0
0 0 0
1 0 3
0 0 0
7 0 9
Explanation For Sample Input 1 :
For First Case - Similar to the example explained above. 

For Second Case - 
Only the cell (2,2) has zero. So all the elements of the second row and second column are changed to zeros.
Sample Input 2 :
2
4 2
1 0
2 7
3 0
4 8
3 3
0 2 3
1 0 3
1 2 0
Sample Output 2 :
0 0
2 0
0 0
4 0
0 0 0
0 0 0
0 0 0
Hint

We can simulate the process described in the statement naively.

Approaches (3)
Brute-Force Approach

The basic idea is to maintain another boolean matrix ‘isZero’ which stores whether our resultant matrix should contain a zero at a particular index or not. We can traverse every element of our original matrix. If the element is 0, then we traverse the complete row and complete column of that particular element and set isZero values accordingly to true for all the elements in that row and column.

 

Algorithm: 

 

setZeros(matrix)

  • Store dimensions of the matrix in n and m
  • Declare “isZero” boolean matrix of size n x m.
  • Iterate over i from 0 to n
    • Iterate over j from 0 to m
      • If matrix[i][j] == 0
        • Iterate over k from 0 to n
          • Set isZero[k][j] = true
        • Iterate over k from 0 to m
          • Set isZero[i][k] = true
  • Iterate over i from 0 to n
    • Iterate over j from 0 to m
      • If isZero[i][j] == true
        • Set matrix[i][j] = 0
Time Complexity

O(N * M * (M + N)) where N & M are dimensions of the given matrix.
 

We are traversing each element. For each element that is zero, we are traversing its complete row and column. So we have O(M * N) elements and for each element, we can traverse a row and a column in the worst case, i.e. O(M + N). So total complexity is O(M * N * (M + N).

Space Complexity

O(N * M) where N & M are dimensions of the given matrix.

 

We need to declare a 2D boolean matrix of size n x m. So the total required space will be O(N * M).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Set Matrix Zeros
Full screen
Console