4.28.3 — Set Matrix Zeroes

LeetCode 73 · Medium

The problem

If any cell is 0, set its entire row and column to 0. Do it in place.

1 1 1        1 0 1
1 0 1   →    0 0 0
1 1 1        1 0 1

The follow-up asks for O(1) extra space.

Why the naive version is wrong

Setting rows and columns to zero as you find zeros corrupts the input as you read it — a zero you just wrote is indistinguishable from a zero that was there originally, so it triggers more clearing, and eventually the whole matrix is zero.

So you must record everything first, then apply. Two passes, always.

The easy version keeps two sets of the rows and columns to clear — O(m + n) space — and that is a perfectly good first answer.

The O(1)-space idea

Use the matrix's own first row and first column as the record.

If matrix[r][c] is 0, write a 0 into matrix[r][0] and matrix[0][c]. Those marks live inside the matrix, so no extra memory is used — and both cells are going to be zeroed anyway, so nothing is lost.

Except for one collision, and it is the whole difficulty.

matrix[0][0] would have to record both "clear row 0" and "clear column 0", and it can only hold one.

The fix is a single extra boolean. Handle the first column with its own flag, and let matrix[0][0] mean "clear row 0".

The four passes

1. Scan the first column. If any cell is 0, remember it in first_col_zero.
2. Scan the rest of the matrix, from row 0 and column 1. Mark zeros in matrix[r][0] and matrix[0][c].
3. Apply, from the inside out. Walk rows 1 onward and columns 1 onward, zeroing any cell whose row or column marker is 0.
4. Apply the first row and first column last, using matrix[0][0] and first_col_zero.

Pass 3 must go before pass 4. If you cleared the first row first, its markers would be destroyed before the inner cells had used them. Order is the correctness argument for this whole solution.

The solution

Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_col_zero = False

        # 1 & 2: record, using row 0 and column 0 as the markers
        for r in range(rows):
            if matrix[r][0] == 0:
                first_col_zero = True                  # column 0 needs clearing

            for c in range(1, cols):                   # start at 1, not 0
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        # 3: apply to the interior, bottom-right first is not required — but
        #    the first row and column must not be cleared yet
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        # 4a: the first row, decided by matrix[0][0]
        if matrix[0][0] == 0:
            for c in range(cols):
                matrix[0][c] = 0

        # 4b: the first column, decided by the flag
        if first_col_zero:
            for r in range(rows):
                matrix[r][0] = 0

TypeScript

function setZeroes(matrix: number[][]): void {
  const rows = matrix.length, cols = matrix[0].length;
  let firstColZero = false;

  for (let r = 0; r < rows; r++) {
    if (matrix[r][0] === 0) firstColZero = true;
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }

  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }

  if (matrix[0][0] === 0) {
    for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  }

  if (firstColZero) {
    for (let r = 0; r < rows; r++) matrix[r][0] = 0;
  }
}

The inner loop of pass 1 starts at column 1. Column 0 is handled by the flag, so reading it as a normal cell would confuse the two roles.

matrix[0][0] means "clear row 0", and the separate flag means "clear column 0". Splitting the two meanings is the entire trick.

Pass 3 runs before pass 4, so the markers survive until they have been used.

Trace

0 1 2 0
3 4 5 2
1 3 1 5

Pass 1: matrix[0][0] is 0 → first_col_zero = True. The 0 at (0,3) sets matrix[0][0] = 0 (already) and matrix[0][3] = 0 (already).

After recording, row 0 is 0 1 2 0, and no other row has a zero in columns 1 onward.

Pass 3: for r in 1..2, c in 1..3 — clear where matrix[r][0] == 0 (no) or matrix[0][c] == 0 (true for c = 3). So (1,3) and (2,3) become 0.

Pass 4a: matrix[0][0] is 0 → clear all of row 0.

Pass 4b: flag is true → clear all of column 0.

0 0 0 0
0 4 5 0
0 3 1 0

✓

Complexity

O(mn) time, O(1) extra space.

The set-based version is O(m + n) space and much easier to write.

Which to write

Write the O(m+n) version first, say its space cost, then offer this one when the follow-up comes. It is short:

zero_rows = {r for r in range(rows) for c in range(cols) if matrix[r][c] == 0}
zero_cols = {c for r in range(rows) for c in range(cols) if matrix[r][c] == 0}
for r in range(rows):
    for c in range(cols):
        if r in zero_rows or c in zero_cols:
            matrix[r][c] = 0

The O(1) version is not better in any practical sense — O(m + n) is tiny — so its value is entirely as a demonstration that you can use the data structure itself as scratch space. Say that honestly rather than pretending it matters.

Where this goes next

The idea — store state inside the data you already have — recurs:

• Find the Duplicate Number by negating nums[abs(x)] as a visited flag, when mutation is allowed. 4.9.8.
• First Missing Positive — place each value at its own index, using the array as its own hash table.
• Number of Islands — the grid is the visited set. 4.20.1.
• Copy List with Random Pointer — weaving copies into the original list. 4.9.5.

Every one of them trades clarity for memory, and every one of them mutates the input — which is a real cost outside a coding judge.

What the interviewer will push on

"Why can't you clear as you scan?" Written zeros are indistinguishable from original ones, so the clearing cascades.

"Where do you store the markers, and what collides?" The first row and column, and matrix[0][0] has two jobs — hence the extra flag.

"Why must the interior be cleared before the first row and column?" Otherwise the markers are destroyed before use.

"Is O(1) space actually worth it here?" Honestly, no — O(m+n) is negligible. Say so; it shows judgement rather than reflex.

One thing to volunteer: name the collision at matrix[0][0] before writing any code. It is the only genuinely hard part, and stating it first makes the four passes look inevitable.

Next: 4.28.4 Happy Number — cycle detection somewhere you would not expect it.