LeetCode 73 · Math & Geometry · concept: math-and-geometry
Problem
If a cell is 0, set its entire row and column to 0 — in place, ideally O(1) extra space.
The trap — do it in the wrong order
Zeroing rows/columns as you find zeros corrupts the grid: the new zeros trigger more rows/columns to be cleared. You must first record which rows and columns need zeroing, then apply.
Approach — use the first row/column as markers (O(1) space)
Instead of O(m+n) marker arrays, store the flags in the matrix’s own first row and column. Two extra booleans remember whether the first row / first column were themselves originally zero.
def setZeroes(matrix):
rows, cols = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
first_col_zero = any(matrix[r][0] == 0 for r in range(rows))
for r in range(1, rows): # mark in row 0 / col 0
for c in range(1, cols):
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
for r in range(1, rows): # apply from the markers
for c in range(1, cols):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
if first_row_zero: # handle the marker row/col last
for c in range(cols): matrix[0][c] = 0
if first_col_zero:
for r in range(rows): matrix[r][0] = 0Time O(m·n), space O(1).
Reusing the input as scratch space
The first row and column serve as the “which rows/cols to zero” registers — the matrix stores its own metadata. The two booleans are needed because those marker cells can’t record their own original-zero status (they’d be overwritten). Record-then-apply, in the right order, is essential.
Key insight
O(1)-space in-place transforms → reuse part of the input as your bookkeeping. Folding the marker arrays into row 0 / column 0 is the space-saving trick; the deeper lesson is separating the detect phase from the mutate phase so writes don’t corrupt reads.
Related
- concept: math-and-geometry
- prev: Spiral Matrix · next: Happy Number
Software engineering
Infrastructure & security
Computer science
Hardware & engineering