Set Matrix Zeroes
Clear the row and column of every zero — using the grid itself as the notepad, so no extra memory is needed
Problem Statement
If an element is 0, set its entire row and column to 0. Do it in place.
Input: [[1,1,1], Output: [[1,0,1],
[1,0,1], [0,0,0],
[1,1,1]] [1,0,1]]
Input: [[0,1,2,0], Output: [[0,0,0,0],
[3,4,5,2], [0,4,5,0],
[1,3,1,5]] [0,3,1,0]]Intuition
The trap is clearing as you go. Set a row to zero and the new zeros look exactly like original zeros — so the next pass clears their columns too, and the whole grid collapses.
[[1,1,1], clear row 1 immediately [[1,0,1],
[1,0,1], → then see the new zeros → [0,0,0], → everything
[1,1,1]] and clear their columns [1,0,1]] eventually 0So the work must happen in two phases: find every zero first, then clear.
The obvious way is two sets — which rows, which columns — costing O(rows + cols) memory. That is a fine answer. But the problem wants O(1).
The insight
There is already somewhere to write: the first row and first column of the grid itself.
If grid[r][c] is zero, mark grid[r][0] = 0 and grid[0][c] = 0. Those marks live exactly where the clearing will happen anyway — a row that needs clearing will have its first cell zeroed regardless.
The two sets become two lines of the grid you already have.
The catch: grid[0][0] sits in both the row markers and the column markers. It cannot mean two things at once — so one extra boolean tracks the first column separately.
Approach
Record whether the first column contains a zero
One boolean. This is the piece grid[0][0] cannot represent, because it is doing duty as a row marker.
Mark: scan from (0, 1) onwards
For each zero found, set grid[r][0] = 0 and grid[0][c] = 0.
Clear the interior, working from (1, 1)
A cell is zeroed if its row marker or its column marker is zero. Do the interior before the markers, or you erase the information you are reading.
Handle row 0, then column 0 — in that order
If grid[0][0] is zero, clear the first row. Then if the boolean was set, clear the first column.
Solution
def set_zeroes(matrix: list[list[int]]) -> None:
"""Zero the row and column of every zero, in place, O(1) space.
The first row and column store which rows/columns to clear.
"""
rows, cols = len(matrix), len(matrix[0])
first_col_has_zero = any(matrix[r][0] == 0 for r in range(rows))
# Mark. Skip column 0 — the boolean above owns it.
for r in range(rows):
for c in range(1, cols):
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
# Clear the interior, reading the markers.
for r in range(1, rows):
for c in range(1, cols):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
# Now the markers themselves — row 0 first.
if matrix[0][0] == 0:
for c in range(cols):
matrix[0][c] = 0
if first_col_has_zero:
for r in range(rows):
matrix[r][0] = 0Three ordering rules, all load-bearing
| Rule | Break it and… |
|---|---|
| Clear the interior before the marker lines | You erase the markers, then read them as "no zero here" |
| Handle row 0 before column 0 | grid[0][0] gets cleared, losing the row-0 signal |
| Track the first column with a separate boolean | grid[0][0] cannot mean both "row 0 has a zero" and "column 0 has a zero" |
Each of these fails on a specific input rather than all of them, which is what makes this problem harder than it looks.
Complexity Analysis
Time Complexity
O(rows × cols)
Space Complexity
O(1)
Time — a constant number of passes over the grid.
Space — one boolean. The O(rows + cols) version using two sets is easier to write and correct; this one is what the problem is actually testing.
Edge Cases
Related Problems
- Rotate Image — another in-place transform where write order matters
- Product of Array Except Self — using the output array as working storage
- Matrix — the in-place techniques compared