Last Updated: 25 Jan, 2022

Set Matrix Zeros

Easy

Asked in companies

Solve now

Problem statement

Given an ‘N’ x ‘M’ integer matrix, if an element is 0, set its entire row and column to 0's, and return the matrix. In particular, your task is to modify it in such a way that if a cell has a value 0 (matrix[i][j] == 0), then all the cells of the ith row and jth column should be changed to 0.

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]

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?

Solve now

Approaches

01 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

Solve now

02 Approach

The basic idea is to keep track of each row and each column and maintain two boolean arrays ‘rowZero’ and ‘colZero’ to store whether a particular row should be filled with all zeros or not and similarly another one for columns. We traverse each element and if the element is equal to 0 in the original matrix then we set ‘rowZero’ of its row and ‘colZero’ of its column to true. We iterate over ‘rowZero’ and set all the elements of all the rows to zero whose ‘rowZero’ is true and the same with columns while iterating on ‘colZero’.

Algorithm:

setZeros(matrix)

Store dimensions of matrix in n and m.
Declare boolean arrays “rowZero” and “colZero” of size n and m respectively.
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If matrix[i][j] == 0
    - Set colZero[j] = true
    - Set rowZero[i] = true
Iterate over i from 0 to n
- Iterate over j from 0 to m
  - If rowZero[i] is true or colZero[j] is true
    - Set matrix[i][j] = 0

Solve now

03 Approach

The basic idea is to store whether a complete row and complete column should be zero or not but instead of declaring extra memory for this purpose, we are using the first row and first column of the original matrix to store this information. We are using two independent variables to store these values for the first row and first column. So we only need constant space for those two variables. Like the last approach we first find out whether a row should or column should be filled with all zeros or not. And after that, the eligible rows and columns are filled with zeros.

Algorithm:

setZeros(matrix)

Store dimensions of the matrix in n and m.
Declare boolean variables “firstRowZero” and “firstColZero” and initialize them to false.
Traverse over the first row and if any of it is zero then set firstRowZero to true.
Traverse over the first column and if any of it is zero then set firstColZero to true.
Iterate over i from 1 to n
- Iterate over j from 1 to m
  - If matrix[i][j] == 0
    - Set matrix[i][0] = 0
    - Set matrix[0][j] = 0
Iterate over i from 1 to n
- Iterate over j from 1 to m
  - If matrix[i][0] == 0 or matrix[0][j] == 0
    - Set matrix[i][j] = 0
If “firstColZero” is true
- Iterate over i from 0 to n
  - Set matrix[i][0] = 0
If “firstColZero” is true
- Iterate over j from 0 to m
  - Set matrix[0][j] = 0

Solve now