TL;DR
Use the first row and first column as marker arrays (plus two flags) to zero rows/columns in place — O(m·n) time, O(1) extra space.
Approach 1 — Naive: record rows and columns in sets
The only correctness trap is cascading: a zero you write must not cause more clearing. Separate detection from action. First scan the whole matrix and record every row index and column index that contains an original zero, then clear.
from typing import List
def setZeroes(matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
zero_rows, zero_cols = set(), set()
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
zero_rows.add(i)
zero_cols.add(j)
for i in range(m):
for j in range(n):
if i in zero_rows or j in zero_cols:
matrix[i][j] = 0
Complexity: O(m·n) time, O(m + n) extra space for the two sets.
This is correct and readable. The follow-up is to do it without those auxiliary sets.
Approach 2 — Markers in the first row and column (O(1) space)
The matrix itself has space to store the row/column flags. Let cell (i, 0) mark “row i must be cleared” and cell (0, j) mark “column j must be cleared.” The only conflict is the overlap: the first row and first column share cell (0,0) and are themselves data. Track those two with separate boolean flags and process the first row and column last.
from typing import List
def setZeroes(matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_zero = any(matrix[i][0] == 0 for i in range(m))
# use row 0 and column 0 as marker arrays for the inner cells
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# clear inner cells based on the markers
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# finally clear the first row / column if flagged
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
Walkthrough with [[0,1,2,0],[3,4,5,2],[1,3,1,5]] (m=3, n=4):
- Scan first row → contains zeros (
0 at cols 0 and 3) → first_row_zero = True. First column has 0 at (0,0) → first_col_zero = True.
- Mark inner cells (rows/cols ≥ 1): no inner zeros exist here, so the markers set by the inner scan come only from row 0 / col 0 already being
0.
- Apply markers to inner cells: column 3’s marker
matrix[0][3] = 0 clears (1,3) and (2,3); column 0’s marker matrix[0][0] = 0 clears (1,0) and (2,0). Grid so far: [[0,1,2,0],[0,4,5,0],[0,3,1,0]].
first_row_zero → clear row 0 fully: [0,0,0,0]. first_col_zero → clear column 0 (already 0).- Final:
[[0,0,0,0],[0,4,5,0],[0,3,1,0]]. Matches the expected output.
Complexity: O(m·n) time, O(1) extra space — the two boolean flags are the only auxiliary storage.
Common pitfalls
- Clearing a row/column the instant you see a
0, which cascades and zeroes cells that were originally nonzero. Always detect first, apply second.
- Forgetting the two overlap flags for the first row and first column, or computing them after the inner scan has already overwritten
(0,0).
- Processing the first row/column before the inner cells — the markers live there, so wipe them last.
- Using
matrix[0][0] alone to encode both first-row and first-column state without a second flag; one cell can’t safely represent both.
Pattern takeaway
When a problem forbids extra space, look for room inside the input itself. Reusing the border row and column as bookkeeping arrays is the standard technique here. The general recipe, separating a detect pass from an apply pass and storing flags in cells you process last, recurs across in-place grid problems.