The problem is as follows: Given an matrix with m rows and n columns, if an element of the matrix is zero, set its entire row and column as zero. This has to be done in-place.

The trick in this question is that you cannot iterate over the matrix element by element and set the matrix rows and columns as zero where the matrix element is zero because that wouldn't be replacing it in place.

There are two approaches:

• Brute force O(N^3) time
• Optimized Approach O(N^2) time

Input Format:

The first and the only argument of input contains a 2-d integer matrix, A, of size M x N.

Output Format:

Return a 2-d matrix that satisfies the given conditions.

Constraints:

1 <= N, M <= 1000
0 <= A[i][j] <= 1

For Example :
Input:

[   
    [1, 0, 1],
    [1, 1, 1],
    [1, 0, 1]
]

Output:

[   
    [0, 0, 0],
    [1, 0, 1],
    [0, 0, 0]   
]

Note: This will be evaluated on the extra memory used. Try to minimize the space and time complexity.

Optimized Approach

• We iterate the entire matrix and when we see an element as zero, we make the first element of the corresponding row and column as zero.
• This way we keep track of the entire column and row.
• We pay special attention to first row and olumn becuase these are the starting indices for us.
• Thus isCol keeps track of first column.
• We now iterate the entire matrix except first row and first column and change the matrix elements to zero if either the corresponding row's first element or column's first element is zero.

The time complexity of this approach is O(N^2) as we traverse each element only twice.

Solution

class Solution {
  public void setZeroes(int[][] matrix) {
    Boolean isCol = false;
    int R = matrix.length;
    int C = matrix[0].length;

    for (int i = 0; i < R; i++) {

    //Since first cell for both first row and
    //first column is the same i.e. matrix[0][0]
    // We can use an additional variable for
    //either the first row/column.
    // For this solution we are using an
    //additional variable for the first column
    // and using matrix[0][0] for the first row.
      if (matrix[i][0] == 0) {
        isCol = true;
      }

      for (int j = 1; j < C; j++) {
        // If an element is zero, we set
        //the first element of the corresponding
        //row and column to 0
        if (matrix[i][j] == 0) {
          matrix[0][j] = 0;
          matrix[i][0] = 0;
        }
      }
    }

    // Iterate over the array once again and using the first row and first column, update the elements.
    for (int i = 1; i < R; i++) {
      for (int j = 1; j < C; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
          matrix[i][j] = 0;
        }
      }
    }

    // See if the first row needs to be set to zero as well
    if (matrix[0][0] == 0) {
      for (int j = 0; j < C; j++) {
        matrix[0][j] = 0;
      }
    }

    // See if the first column needs to be set to zero as well
    if (isCol) {
      for (int i = 0; i < R; i++) {
        matrix[i][0] = 0;
      }
    }
  }
}

Input:

[
      [1,1,1],
      [1,0,1],
      [1,1,1]
]

Output:

[
      [1,0,1],
      [0,0,0],
      [1,0,1]
]

Steps through the algorithm using an example

1. We iterate through the matrix to find out if firstCol exists. But we find out no row has first elements as zero

Initially,
[   
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
isCol=false;

2. Next we iterate the matrix row by row and if we find an element zero we set the first element in its respective row and column as zero. Thus, (0,1) and (1,0) are set to zero.

[   
    [1, 0, 1],
    [0, 0, 1],
    [1, 1, 1]
]

3. We now again iterate the array again row by row and set elemnets to zero if the first element of their row or column is zero.

[   
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1]
]

Complexity : The complexity of the above approach is O(N^2) where there are N rows or N columns in the Matrix or O(N^2) elements in the matrix.

With this article at OpenGenus, you must have the complete idea of this problem of setting elements of a Matrix to zero based on given condition. Enjoy.