Set Matrix Zeroes

Signal

"Need O(rows + cols) of bookkeeping but must use O(1) space" — when the extra space you'd want is smaller than the input itself, look for unused capacity inside the input to store it. Here, the first row and first column double as marker storage, since you're already about to overwrite them.

Approach

Before touching anything, record two booleans: whether the first row originally contains a zero, and whether the first column does — both are about to become marker storage, so this is the only chance to know their original state. Then scan the interior (rows/cols 1 and up): whenever a cell is 0, mark its row by zeroing matrix[i][0] and its column by zeroing matrix[0][j]. In a second interior pass, zero any cell whose row-marker or column-marker was set. Finally, zero the first row and/or first column themselves if their saved booleans say they originally held a zero.

Skeleton

first_row_has_zero = any zero in row 0
first_col_has_zero = any zero in col 0

for i in 1..rows, j in 1..cols:
    if matrix[i][j] == 0:
        matrix[i][0] = 0
        matrix[0][j] = 0

for i in 1..rows, j in 1..cols:
    if matrix[i][0] == 0 or matrix[0][j] == 0:
        matrix[i][j] = 0

if first_row_has_zero: zero row 0
if first_col_has_zero: zero col 0

Solution

def set_zeroes(matrix: list[list[int]]) -> None:
    rows, cols = len(matrix), len(matrix[0])
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(rows))

    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_has_zero:
        for j in range(cols):
            matrix[0][j] = 0

    if first_col_has_zero:
        for i in range(rows):
            matrix[i][0] = 0

Complexity

O(rows · cols) time — a constant number of full passes over the matrix. O(1) extra space — the markers live inside the matrix itself instead of a separate set.

Pitfalls

• Capturing the "first row/col originally had a zero" booleans after starting to write markers into row 0 / col 0 loses that information — capture them first, before any marker writes.
• Zeroing cells during the very first scan (instead of only marking) cascades: an original zero would immediately wipe its whole row/column while you're still scanning, over-zeroing neighbors that shouldn't be touched yet. Mark first, apply second.
• Letting the interior double-loops start at index 0 mixes markers with real data — they must start at index 1, with row 0 / col 0 handled only in the final step.