Set Matrix Zeroes Solution

Problem

Given an m × n grid of integers, find every cell containing 0 and set all cells in its row and column to 0 as well — modifying the grid in-place. The key constraint is that zeroing must reflect the original zeros only: a cell turned zero by this process must not cascade further.

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: The single zero at (1,1) zeroes out all of row 1 and all of column 1.

Counter-example — [[0,1],[1,1]] becomes [[0,0],[0,1]], not [[0,0],[0,0]], because only the original zero at (0,0) triggers propagation.

Intuition

The problem reduces to: record which rows and columns contain a zero, then do a second sweep and zero every cell whose row or column is in that record. The challenge is doing that recording without extra space: the first row and first column of the matrix can serve as the record themselves, as long as you save whether they originally held zeros before overwriting them.

Approach 1 — Hash Sets (Extra Space)

Scan the matrix once to collect which rows and columns contain a zero, then scan again and zero any cell whose row or column appears in either set.

Initialize an empty set for zero rows and another for zero columns.
Scan every cell; when matrix[i][j] == 0, add i to zero rows and j to zero columns.
Scan every cell again; if its row index is in zero rows or its column index is in zero columns, set it to 0.

1def setZeroes(matrix: list[list[int]]) -> None:
2    rows, cols = len(matrix), len(matrix[0])
3    zero_rows: set[int] = set()
4    zero_cols: set[int] = set()
5
6    for i in range(rows):
7        for j in range(cols):
8            if matrix[i][j] == 0:
9                zero_rows.add(i)
10                zero_cols.add(j)
11
12    for i in range(rows):
13        for j in range(cols):
14            if i in zero_rows or j in zero_cols:
15                matrix[i][j] = 0

Time: O(m·n) — two full matrix scans.
Space: O(m+n) — one set per dimension.

Approach 2 — In-Place Markers (Constant Space)

Use matrix[i][0] (first column) to mark whether row i needs zeroing, and matrix[0][j] (first row) to mark whether column j needs zeroing. Save flags for the first row and first column themselves before they get overwritten as markers.

Check whether the first row contains any zero; save in first_row_has_zero.
Check whether the first column contains any zero; save in first_col_has_zero.
For every inner cell (row ≥ 1, col ≥ 1) that equals 0, mark matrix[i][0] = 0 and matrix[0][j] = 0.
For every inner cell, if its row marker or column marker is 0, zero that cell.
If first_row_has_zero, zero the entire first row.
If first_col_has_zero, zero the entire first column.

1def setZeroes(matrix: list[list[int]]) -> None:
2    rows, cols = len(matrix), len(matrix[0])
3
4    # Save original state of the first row and column before using them as markers
5    first_row_has_zero = any(matrix[0][j] == 0 for j in range(cols))
6    first_col_has_zero = any(matrix[i][0] == 0 for i in range(rows))
7
8    # Mark zero rows/cols using first row and first column as scratch space
9    for i in range(1, rows):
10        for j in range(1, cols):
11            if matrix[i][j] == 0:
12                matrix[i][0] = 0  # row i needs zeroing
13                matrix[0][j] = 0  # col j needs zeroing
14
15    # Apply markers to inner cells only — first row/col handled separately below
16    for i in range(1, rows):
17        for j in range(1, cols):
18            if matrix[i][0] == 0 or matrix[0][j] == 0:
19                matrix[i][j] = 0
20
21    # Now zero the first row and column based on their original state
22    if first_row_has_zero:
23        for j in range(cols):
24            matrix[0][j] = 0
25    if first_col_has_zero:
26        for i in range(rows):
27            matrix[i][0] = 0

Time: O(m·n) — three passes over the matrix, each O(mn).
Space: O(1) — only two boolean flags; the first row/column serve as in-place markers.

Complexity Summary

Approach	Time	Space	When to use
Hash Sets	O(m·n)	O(m+n)	When code clarity matters more than memory
In-Place Markers	O(m·n)	O(1)	Interview follow-up asking for constant extra space

Common Mistakes

Zeroing during the first scan — if you set cells to 0 as you find them, a newly-zeroed cell in row 2 can incorrectly trigger zeroing in row 3's column, which was non-zero in the original matrix. Always collect all zero locations before applying them.
Processing the first row/column before inner cells in the O(1) approach — the markers live in row 0 and column 0, so zeroing them early destroys the information needed to update inner cells.
Forgetting to handle the first row and first column separately — they function as the marker arrays, so their own zeroing must be deferred to the final step.
Using a sentinel value (like -1 or INT_MIN) to tag cells — the problem allows negative integers, so any sentinel could collide with a legitimate value in the matrix.
Checking first_col_has_zero against matrix[0][0] — matrix[0][0] is shared between the first-row marker and the first-column marker; reading it after marking has already begun gives the wrong answer.

Set Matrix Zeroes — Solution