Set Matrix Zeroes
Set Matrix Zeroes: if a cell is 0, set its entire row and column to 0 — in place.
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2³¹ <= matrix[i][j] <= 2³¹ - 1
Intuition
Set matrix zeroes sets an entire row and column to zero wherever a zero appears. The trap is immediate and catches nearly everyone on the first attempt.
Zeroing rows and columns as you scan corrupts the input. A zero written by one operation is indistinguishable from an original zero, so the next scan step treats it as a new trigger and cascades until the whole matrix is zero.
So the positions must be recorded first and applied afterwards. Two sets of row and column indices solve it at O(m + n) space.
The follow-up asks for O(1) space, and the technique is to store the markers inside the matrix itself:
- Use the first row and first column as the marker arrays — if matrix[i][j] is zero, set matrix[i][0] and matrix[0][j] to zero.
Those cells are exactly the ones that will be zeroed anyway, so overwriting them destroys nothing that is still needed.
One conflict remains: matrix[0][0] serves as the marker for both the first row and the first column, and cannot represent both independently. The fix is a separate boolean recording whether the first column originally contained a zero, with matrix[0][0] handling the first row alone.
The application order is what makes it work. Process the interior cells first, reading their markers, then handle the first row and column last. Doing the first row early destroys the markers the interior still needs.
Processing the interior in reverse — from the bottom-right — is another way to guarantee markers are read before being overwritten.
Both versions are O(m × n) time; the marker version reaches O(1) space.
The trap is that zeroing as you scan corrupts the very data you're still reading. So the fix is two phases: record which rows and columns are doomed, then apply. Separating detection from mutation is the general lesson for any in-place grid transform where a write can be mistaken for input.
Approach
Before reading on: price up what the direct approach costs here, then ask whether the traversal can carry its state across rows instead of restarting. Aim for O(m·n) time and O(m + n) space.
See why in-place scanning fails
A zero written by one operation looks identical to an original zero, so the scan retriggers on it and cascades until the whole matrix is zero.
Record first, apply second
Collect the rows and columns needing zeroing, then apply them in a second pass. Two sets solve it at O(m + n) space.
Store markers in the matrix
For O(1) space, use the first row and column as the marker arrays. Those cells will be zeroed anyway, so overwriting them loses nothing needed.
Resolve the corner conflict
matrix[0][0] cannot mark both the first row and first column. Use a separate boolean for the first column and let the corner cover the first row.
Apply to the interior first
Process interior cells before the first row and column. Handling the borders early destroys the markers the interior still needs to read.
Or iterate in reverse
Working from the bottom-right guarantees each marker is read before it can be overwritten — an alternative to ordering the passes.
Cost of the approaches
Both are O(m × n) time. The set-based version uses O(m + n) space; the marker version achieves O(1).
Solution & live demo
Common pitfalls
Zeroing during the scan
for i, row in enumerate(matrix):
for j, v in enumerate(row):
if v == 0:
for k in range(len(row)): matrix[i][k] = 0# phase 1: collect rows/cols # phase 2: apply
The zeros you write are indistinguishable from original zeros, so they trigger further clearing and the whole matrix cascades to zero. Detection must finish before any mutation starts.
Storing coordinates instead of row and column indices
zeros = [(i, j) for ...] for i, j in zeros: matrix[i][j] = 0
rows, cols = set(), set() ... if i in rows or j in cols: row[j] = 0
Recording the cell only re-zeroes that one cell. What must be cleared is the entire row and the entire column it sits in, so the indices are what matter.
Assuming the O(1)-space version is required
# elaborate first-row/first-column marker scheme
rows, cols = set(), set()
The marker trick reduces space to O(1) but is fiddly and easy to get wrong. Two sets are O(m + n) — usually acceptable — and the interviewer generally wants to see this working first before you optimise.
Edge cases
Both sets stay empty, so the second pass changes nothing.
Every row and column is flagged; the whole matrix stays zero after the second pass.
Set membership is idempotent, so overlapping flags simply zero the cell once.