medium Set Matrix Zeroes

Problem Statement

Given a 2D grid of numbers called matrix, if any number in the grid is 0, set the entire row and column containing that zero to zeros.

The grid should be modified in place without using any extra grid.

Examples

Example 1:

• Input: matrix =

[[2, 3, 4], 
 [5, 0, 6], 
 [7, 8, 9]]

• Expected Output:

[[2, 0, 4], 
 [0, 0, 0], 
 [7, 0, 9]]

• Justification: The element at position (1, 1) is zero. So, the second row and column are set to zero.

Example 2:

• Input: matrix =

[[0, 2, 3], 
 [4, 5, 6], 
 [7, 8, 9]]

• Expected Output:

[[0, 0, 0], 
 [0, 5, 6], 
 [0, 8, 9]]

• Justification: The element at position (0, 0) is zero. So, the first row and column are set to zero.

Example 3:

• Input: matrix =

[[1, 2, 3, 7], 
 [4, 0, 6, 8], 
 [0, 8, 9, 6],
 [1, 4, 6, 4]]

• Expected Output:

[[0, 0, 3, 7], 
 [0, 0, 0, 0], 
 [0, 0, 0, 0],
 [0, 0, 6, 4]

• Justification: The elements at position (1, 1), and (2, 0) are zero. So, the respected rows and columns are set to zero.

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2³¹ <= matrix[i][j] <= 2³¹ - 1

Solution

To solve this problem, we use the first row and first column of the matrix to mark the rows and columns that need to be set to zero. This way, we can avoid using extra space for marking. Initially, we traverse the matrix to find the cells that contain zeros. If a cell at position (i, j) is zero, we set the first cell of the i-th row and the first cell of the j-th column to zero. We also use a boolean variable to track if the first column itself needs to be zeroed.

This approach works because we are only modifying the first row and first column during the first pass. In the second pass, we use these markers to set the appropriate cells to zero. Finally, we handle the first row and first column separately to ensure the markers themselves do not interfere with the zeroing process. This method ensures the solution is both space-efficient and straightforward.

Step-by-Step Algorithm

1. Initialize: Create a boolean variable isCol and set it to false. This will track if the first column needs to be zeroed.
2. First Pass:
   • Loop through each element of the matrix.
   • If any element in the first column is zero, set isCol to true.
   • For each zero element in the matrix (not in the first column), set the first element of its row and column to zero.
3. Second Pass:
   • Loop through the matrix starting from the second row and second column.
   • If the first element of the row or column is zero, set the corresponding element to zero.
4. Handle First Row:
   • If the first element of the first row is zero, set all elements in the first row to zero.
5. Handle First Column:
   • If isCol is true, set all elements in the first column to zero.
6. Return the matrix.

Algorithm Walkthrough

• Initial matrix:

[[1, 2, 3, 7], 
 [4, 0, 6, 8], 
 [0, 8, 9, 6], 
 [1, 4, 6, 4]]

• First Pass:

  • Check each element:
    • (0,1) → 2 (not zero)
    • (0,2) → 3 (not zero)
    • (0,3) → 7 (not zero)
    • (1,0) → 4 (not zero)
    • (1,1) → 0 (zero, mark matrix[0][1] = 0, mark matrix[1][0] = 0)
    • (1,2) → 6 (not zero)
    • (1,3) → 8 (not zero)
    • (2,0) → 0 (zero, set isCol to true, mark matrix[0][0] = 0, mark matrix[2][0] = 0)
    • (2,1) → 8 (not zero)
    • (2,2) → 9 (not zero)
    • (2,3) → 6 (not zero)
    • (3,0) → 1 (not zero)
    • (3,1) → 4 (not zero)
    • (3,2) → 6 (not zero)
    • (3,3) → 4 (not zero)
  • Matrix after marking:

    [[0, 0, 3, 7], 
     [0, 0, 6, 8], 
     [0, 8, 9, 6], 
     [1, 4, 6, 4]]
    

• Second Pass:

  • Check each element starting from the second row and second column:
    • (1,1) → matrix[0][1] is zero (set to zero)
    • (1,2) → matrix[0][2] is not zero, matrix[1][0] is zero (set to zero)
    • (1,3) → matrix[0][3] is not zero, matrix[1][0] is zero (set to zero)
    • (2,1) → matrix[0][1] is zero (set to zero)
    • (2,2) → matrix[0][2] is not zero, matrix[2][0] is zero (set to zero)
    • (2,3) → matrix[0][3] is not zero, matrix[2][0] is zero (set to zero)
    • (3,1) → matrix[0][1] is zero (set to zero)
    • (3,2) → matrix[0][2] is not zero, matrix[3][0] is not zero (remain 6)
    • (3,3) → matrix[0][3] is not zero, matrix[3][0] is not zero (remain 4)
  • Matrix after setting zeros:

     [[0, 0, 3, 7], 
      [0, 0, 0, 0], 
      [0, 0, 0, 0], 
      [1, 0, 6, 4]]
    

• Handle First Row:

  • First element of the first row is not zero, so no need to change the first row.
  • Matrix after setting first row:

    [[0, 0, 3, 7], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [1, 0, 6, 4]]
  

• Handle First Column:

  • isCol is true, set all elements in the first column to zero
  • Final matrix:

    [[0, 0, 3, 7], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 6, 4]]
    

Code

import java.util.Arrays;

public class Solution {

  public int[][] setZeroes(int[][] matrix) {
    boolean isCol = false;
    int R = matrix.length;
    int C = matrix[0].length;

    // First pass: mark rows and columns that need to be zeroed
    for (int i = 0; i < R; i++) {
      if (matrix[i][0] == 0) {
        isCol = true; // Mark the first column for zeroing
      }
      for (int j = 1; j < C; j++) {
        if (matrix[i][j] == 0) {
          matrix[0][j] = 0; // Mark the top cell of this column
          matrix[i][0] = 0; // Mark the start cell of this row
        }
      }
    }

    // Second pass: use the marks to set elements to zero
    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; // Set cell to zero if its row or column is marked
        }
      }
    }

    // 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;
      }
    }

    return matrix; // Return the modified matrix
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    int[][] matrix1 = { { 2, 3, 4 }, { 5, 0, 6 }, { 7, 8, 9 } };
    System.out.println(Arrays.deepToString(solution.setZeroes(matrix1)));
    // Expected: [[2, 0, 4], [0, 0, 0], [7, 0, 9]]

    int[][] matrix2 = { { 0, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
    System.out.println(Arrays.deepToString(solution.setZeroes(matrix2)));
    // Expected: [[0, 0, 0], [0, 5, 6], [0, 8, 9]]

    int[][] matrix3 = {
      { 1, 2, 3, 7 },
      { 4, 0, 6, 8 },
      { 0, 8, 9, 6 },
      { 1, 4, 6, 4 },
    };
    System.out.println(Arrays.deepToString(solution.setZeroes(matrix3)));
    // Expected: [[0, 0, 3, 7], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 6, 4]]
  }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is , where M is the number of rows and N is the number of columns in the matrix. This is because we traverse the matrix twice: once for marking and once for setting zeroes.

Space Complexity

The space complexity of the solution is , as we are not using any extra space that scales with the input size.