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

Pattern

In-place marker rows/cols for O(1) extra space. Naive: store zero-row and zero-col bitsets in O(m+n) space. Optimized: reuse the matrix's first row as column markers and first column as row markers. Because matrix[0][0] is shared by both marker strips, one of them needs an external flag (isCol here for "first column must zero"). Order of finalization is mandatory: zero the interior using markers first, then zero the first row if matrix[0][0] was marked, then zero the first column if isCol.

When-not: if a full copy of the matrix is allowed, a two-pass with O(m+n) boolean arrays is clearer and same O(m·n) time. Interview follow-up almost always asks for O(1) extra space after the O(m+n) solution.

Solution

Use the first row and first column as marker storage. Scan for zeros: a zero at (i,j) with j>0 sets matrix[i][0] and matrix[0][j]; a zero in column 0 only sets isCol. Second pass zeros interior cells whose row or column marker is 0. Finally zero the first row if matrix[0][0]==0, then the first column if isCol.

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 at interior cell: mark column via matrix[0][1] = 0, mark row via matrix[1][0] = 0)
    • (1,2) → 6 (not zero)
    • (1,3) → 8 (not zero)
    • (2,0) → 0 (zero in the first column only: set isCol = true; do not write matrix[0][0] from this cell — first-column zeros are tracked only by isCol)
    • (2,1)–(3,3) → non-zeros elsewhere leave markers unchanged
  • Matrix after marking (note matrix[0][0] is still 1 — it is not a marker for column 0):

    [[1, 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:

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

• Handle First Row:

  • matrix[0][0] is still 1, so we do not zero the entire first row from this check. Column-1 is already 0 from the marker; cells (0,2) and (0,3) stay non-zero.
  • Matrix after first-row handling (unchanged top row body):

  [[1, 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.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Set Matrix Zeroes

Why this concept exists (judgment layer)

O(1)-space zeroing reuses first row/col as markers; matrix[0][0] collision forces an external isCol (or isRow) flag and a strict finalization order. This is the classic space-optimization interview upgrade from O(m+n) bool arrays.

Worked example with complexity derivation

matrix=
[[1,2,3,7],
 [4,0,6,8],
 [0,8,9,6],
 [1,4,6,4]]
Mark: (1,1)=0 → matrix[0][1]=0, matrix[1][0]=0; (2,0)=0 → isCol=true only
(do NOT set matrix[0][0] from col0 zeros).
After mark: [[1,0,3,7],[0,0,6,8],[0,8,9,6],[1,4,6,4]].
Zero interior via markers → rows1–2 all zero, col1 zeroed in row3.
matrix[0][0] still 1 → do not wipe row0 body; isCol true → zero col0 → final
[[0,0,3,7],[0,0,0,0],[0,0,0,0],[0,0,6,4]].
Time Θ(m·n) two passes; extra space Θ(1).

Pattern + when-NOT / named alternative

PATTERN: first row = col markers; first col = row markers; one bool for the shared corner conflict; zero interior then borders in order. WHEN NOT: O(m+n) arrays allowed → clearer two-pass without order hazards. If destroying first row/col values is forbidden beyond problem statement — problem allows mutating whole matrix. Sparse copy of zero positions O(z) if z≪m·n sometimes nicer.

Edge case / failure mode

Edges: zero only at [0][0]; entire first row zeros; no zeros identity. Failure: finalizing first column before interior (markers destroyed); treating col0 zero as matrix[0][0]=0 incorrectly wiping row0.

Hostile-panel drills (defend the decision)

Q1. Why is isCol needed?
Model answer: matrix[0][0] is both row0 and col0 marker; col0 zeros must not be encoded only in [0][0].

Q2. Correct finalization order?
Model answer: Interior using markers → first row if matrix[0][0]==0 → first column if isCol.

Q3. O(m+n) vs O(1) trade.
Model answer: Same Θ(m·n) time; O(m+n) easier and non-destructive of marker semantics; O(1) is the follow-up.