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.
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".
Scan the first column. If any cell is 0, remember it in first_col_zero.
Scan the rest of the matrix, from row 0 and column 1. Mark zeros in matrix[r][0] and matrix[0][c].
Apply, from the inside out. Walk rows 1 onward and columns 1 onward, zeroing any cell whose row or column marker is 0.
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.
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: rows, cols = len(matrix), len(matrix[0]) first_col_zero = False # (1) # 1 & 2: record, using row 0 and column 0 as the markers for r in range(rows): # (2) if matrix[r][0] == 0: # (3) first_col_zero = True # column 0 needs clearing for c in range(1, cols): # (4) start at 1, not 0 if matrix[r][c] == 0: matrix[r][0] = 0 # (5) 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): # (6) for c in range(1, cols): if matrix[r][0] == 0 or matrix[0][c] == 0: # (7) matrix[r][c] = 0 # 4a: the first row, decided by matrix[0][0] if matrix[0][0] == 0: # (8) for c in range(cols): matrix[0][c] = 0 # 4b: the first column, decided by the flag if first_col_zero: # (9) for r in range(rows): matrix[r][0] = 0
ts
function setZeroes(matrix: number[][]): void { const rows = matrix.length, cols = matrix[0].length; let firstColZero = false; // (1) for (let r = 0; r < rows; r++) { // (2) if (matrix[r][0] === 0) firstColZero = true; // (3) for (let c = 1; c < cols; c++) { // (4) if (matrix[r][c] === 0) { matrix[r][0] = 0; // (5) matrix[0][c] = 0; } } } for (let r = 1; r < rows; r++) { // (6) for (let c = 1; c < cols; c++) { if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0; // (7) } } if (matrix[0][0] === 0) { // (8) for (let c = 0; c < cols; c++) matrix[0][c] = 0; } if (firstColZero) { // (9) for (let r = 0; r < rows; r++) matrix[r][0] = 0; }}
The idea is to use the grid's own first row and first column as notepads. matrix[0][c] = 0 will mean "column c must be cleared", and matrix[r][0] = 0 will mean "row r must be cleared". The cell matrix[0][0] sits in both, so it can only mean one thing. We let it mean "row 0 must be cleared", and keep a separate flag for column 0.
(1) The extra flag: does column 0 need clearing?
(2) Pass one: look at every row.
(3) A zero in column 0 means column 0 must be cleared. Set the flag rather than writing anywhere.
(4) Look at the other columns of this row, from 1 onward. Column 0 is the notepad, so it is not checked here.
(5) A zero at (r, c) means row r and column c must be cleared. Write that into the two notepads.
(6) Pass two: clear the inside of the grid, every cell not in row 0 or column 0. The notepads must stay untouched until this is done, because they are still being read.
(7) Clear a cell if its row or its column was marked.
(8) Now handle row 0, using matrix[0][0].
(9) Last, handle column 0, using the flag. Column 0 is cleared after row 0 on purpose: clearing it first would set matrix[0][0] to 0, and line (8) would then wrongly clear row 0.
Code Walkthrough (O(1) Space):
Pass 1 (Flag Column 0): We scan the first column (matrix[r][0]). If we find any zero, we set first_col_zero = True.
Pass 2 (Record in Margins): We scan the rest of the matrix (rows 0 \dots m-1, columns 1 \dots n-1). If matrix[r][c] == 0, we write a 0 to the top of its column (matrix[0][c]) and the start of its row (matrix[r][0]).
Pass 3 (Apply to Interior): We scan the interior again (rows 1 \dots m-1, columns 1 \dots n-1). If either its row's marker (matrix[r][0]) or its column's marker (matrix[0][c]) is 0, we set matrix[r][c] = 0.
Pass 4 (Apply to Margins):
If matrix[0][0] == 0, we clear the entire first row.
If first_col_zero is True, we clear the entire first column.
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.
Time Complexity:O(mn). We pass over the matrix multiple times (recording, applying to interior, applying to margins), but it is a constant number of passes over m \times n elements.
Space Complexity:O(1). We use one boolean variable (first_col_zero) and repurpose the input matrix's first row and column as our state storage, requiring no additional arrays.
The set-based version is O(m + n) space and much easier 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:
python
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.
"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.