Set Matrix Zeroes (LeetCode 73)
You get a grid of integers, matrix, with m rows and n columns. Every 0 that the grid holds at the start wipes out its whole row and its whole column: each cell in that row and in that column must end up as 0. Change matrix itself and return nothing.
Only the zeros that are there at the start count. A cell that becomes 0 because of this rule does not wipe out anything further.
A full copy of the grid (O(m * n) extra memory) or one marker per row and per column (O(m + n)) both work. LeetCode's follow-up asks for more: use only O(1) extra memory.
Worked Examples
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]0 sits in the middle, so the middle row and the middle column become 0. The four corners keep their 1.matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]][[0,0,0,0],[0,4,5,0],[0,3,1,0]]0. The middle cells 4, 5, 3, 1 keep their values. This is the trap case: row 0 has zeros of its own, so it must be cleared, but only after the second pass has read the column flags in it.⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Core Insight
Every flag lives in a cell that ends up 0 anyway, so row 0 and column 0 can store the flags without losing any value that is still needed. The only information the flags overwrite is whether row 0 and column 0 had zeros of their own, and two booleans recorded first keep it.
Real-World Scenario & Production Applications
A spreadsheet engine or an image tool that must blank out every row and column touched by a bad reading, on a large grid already in memory, where a second grid (or even a mask per row and column on a small device) is not affordable: the grid's own cells hold the bookkeeping.
Step-by-Step Execution Trace Table
Example 2 (the trap case: row 0 has zeros of its own), matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:
| Step | Line | Result | Why |
|---|---|---|---|
| 1 | first_row_zero = any(...) | True | Row 0 has a 0 at columns 0 and 3; recorded before any flag goes into row 0 |
| 2 | first_col_zero = any(...) | True | Column 0 has a 0 in row 0 |
| 3 | Pass 1 over rows 1-2, columns 1-3 | no flag written | No inner cell is 0; the 0 already at matrix[0][3] works as column 3's flag |
| 4 | Pass 2, r = 1 | [3, 4, 5, 0] | Only matrix[0][3] == 0, so only matrix[1][3] becomes 0 |
| 5 | Pass 2, r = 2 | [1, 3, 1, 0] | Same: column 3's flag |
| 6 | if first_row_zero: | row 0 = [0, 0, 0, 0] | Cleared now, after pass 2 has read every flag in it |
| 7 | if first_col_zero: | column 0 = [0, 0, 0] | Result: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] |
Clearing row 0 before pass 2 would make every matrix[0][c] == 0 true, and pass 2 would zero the whole grid.
| 1 | Every cell of a row or column that holds a zero ends up `0`, so those cells can store the marks without losing any value that is still needed: row 0 flags the columns and column 0 flags the rows. |
| 2 | Keep this true: before pass 2, `matrix[r][0] == 0` means row `r` held a zero and `matrix[0][c] == 0` means column `c` did, while `first_row_zero` and `first_col_zero` keep row 0's and column 0's own answers. |
| 3 | Record the two booleans; pass 1 over `range(1, m)` and `range(1, n)` writes `matrix[r][0] = 0` and `matrix[0][c] = 0` for each zero; pass 2 zeroes `matrix[r][c]` when either flag is `0`; finally clear row 0 and column 0 if their booleans say so. |
| 4 | The trap: compute `first_row_zero` and `first_col_zero` before pass 1, and clear row 0 and column 0 after pass 2. Clearing them first turns every flag to `0` and wipes the whole grid. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The easy answer copies the grid, or keeps one marker per row and per column, and zeroes from those. With no extra memory allowed, the marks need a home inside matrix itself. In-Place Marking looks for cells whose final value is already known: a zero at (r, c) means row r and column c end up all zero, so the first cell of that row, matrix[r][0], and the top cell of that column, matrix[0][c], can hold the marks without losing anything. Pass 1 writes the flags and pass 2 reads them. The only thing the flags overwrite is row 0's and column 0's own information, so two booleans, first_row_zero and first_col_zero, save it before pass 1 and are used last.
🗂️ The Analogy: Sticky Notes on the Edge of the Chart
A teacher must wipe every row and every column of a big wall chart that contains a missing score, and she has no notebook to write in. So she puts a red sticky note on the first square of each affected row and on the top square of each affected column: those squares get wiped anyway. Then she walks the chart again and wipes every square whose row or column has a red note. The top row and the left column carry the notes, so before sticking any note on them she remembers whether they had a missing score of their own, and she wipes them last, once nobody needs their notes.
🔑 Why It Works
Every cell a flag overwrites is a cell the answer sets to 0 anyway, so writing a flag never destroys a value you still need. The first row's and first column's own zeros are the exception, which is why the two booleans are read before any flag is written. Both passes skip row 0 and column 0 (range(1, m), range(1, n)), and row 0 and column 0 are cleared only after pass 2 has read every flag.
Recording row 0 and column 0 too late:
first_row_zeroandfirst_col_zeromust be computed before pass 1 writes any flag. Computed after, a column flag in row 0 looks like an original zero: on[[1,1,1],[1,0,1],[1,1,1]]the whole first row would be wiped.Clearing row 0 or column 0 too early: clear them after pass 2. On
[[0,1,2,0],[3,4,5,2],[1,3,1,5]], clearing row 0 first makes everymatrix[0][c] == 0true, and pass 2 zeroes the whole grid instead of keeping4, 5, 3, 1.One flag for the corner:
matrix[0][0]belongs to row 0 and to column 0, so it can't flag both. A zero only in column 0, as in[[1,2],[0,4]], must not wipe row 0's2; two booleans keep the two answers apart.Passes that include row 0 or column 0: both passes run over
range(1, m)andrange(1, n). A pass 2 that starts at row 0 zeroes row 0 (whenmatrix[0][0] == 0) while later rows still read it as their column flags.Zeroing on sight: writing zeros across row
rand columncas soon asmatrix[r][c] == 0is found makes later cells read those new zeros as original ones, and the zeros spread until most of the grid is0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"wipes out its whole row and its whole column", "in place", and the follow-up "O(1) extra memory": a change that depends on the grid as it was, with no memory for a copy or for one marker per row and column. That is the signal for In-Place Marking: find cells whose final value is already known and keep the marks there.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before pass 2, matrix[r][0] == 0 exactly when row r (for r >= 1) held a zero, and matrix[0][c] == 0 exactly when column c (for c >= 1) held a zero; first_row_zero and first_col_zero keep row 0's and column 0's own answers. Pass 2 zeroes matrix[r][c] when matrix[r][0] == 0 or matrix[0][c] == 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use In-Place Marking: keep the bookkeeping in cells of the input whose final value I already know. A zero at row r, column c means that whole row and that whole column end up zero, so the first cell of row r and the top cell of column c can hold the flags without losing any value that is still needed. Pass one scans the inner cells and writes those flags; pass two zeroes every inner cell whose row flag or column flag is zero. The catch is that row zero and column zero are real data too. So before writing any flag I record two booleans, whether row zero and whether column zero had a zero of their own, and I clear them last, after pass two has read every flag; clearing them first would wipe the whole grid. That's O(M times N) time and
O(1)extra space.
Complexity & Mathematical Proof
O(M * N)
Count the work line by line. first_row_zero reads the N cells of row 0 and first_col_zero the M cells of column 0. Pass 1 and pass 2 each visit the (M - 1) * (N - 1) inner cells once, with O(1) work per cell: one test and at most two writes. Clearing row 0 and column 0 at the end touches at most N + M cells. The total is at most 2(M + N) + 2(M - 1)(N - 1) steps, which is O(M * N).
O(1)
The flags are written into matrix itself, which the problem hands us and changes in place anyway. The extra memory is m, n, the loop indices r and c, and the two booleans first_row_zero and first_col_zero: O(1). A copy of the grid would cost O(M * N), and one marker per row and per column O(M + N).
T(M, N) = (M + N) + 2 · (M - 1)(N - 1) + (M + N) = O(M · N)
Derivation Progression
O(M + N)
any(...) over the N cells of row 0 and the M cells of column 0.
O((M - 1)(N - 1))
Each inner cell: one test matrix[r][c] == 0, and at most two flag writes.
O((M - 1)(N - 1))
Each inner cell: one test of its two flags, and at most one write.
O(M + N)
At most N writes for row 0 and M for column 0.
O(M · N)
Two passes over the grid plus its first row and first column.
Variable Definitions
Number of rows, len(matrix) (at most 200)
Number of columns, len(matrix[0]) (at most 200)
Memory Architecture & Bounds
O(1) No recursion
O(1): first_row_zero, first_col_zero, m, n, r, c; the flags live in matrix
O(1): nothing is returned, matrix is changed in place
Boundary Best / Worst Cases
: every cell is read even when the grid has no zero
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "wipes out its whole row and its whole column", "in place", "O(1) extra memory" (the follow-up). A change that depends on the grid as it was, with no memory for a copy: In-Place Marking, keep the marks in cells whose final value is already known.
Up to cells with values in . Two passes are about cell visits. A copy of the grid costs extra memory and one marker per row and column ; flags in row 0 and column 0 cost .
If a very large grid is processed in horizontal stripes by several workers, row 0 and column 0 become shared state: every worker must finish pass 1 before any worker starts pass 2, and the first row and column are cleared only after the last stripe of pass 2. Values span the whole 32-bit range, so a sentinel such as -1 in place of the flags could collide with real data; writing 0 never does, because those cells end up 0.
Set Matrix Zeroes (LeetCode 73)
You get a grid of integers, matrix, with m rows and n columns. Every 0 that the grid holds at the start wipes out its whole row and its whole column: each cell in that row and in that column must end up as 0. Change matrix itself and return nothing.
Only the zeros that are there at the start count. A cell that becomes 0 because of this rule does not wipe out anything further.
A full copy of the grid (O(m * n) extra memory) or one marker per row and per column (O(m + n)) both work. LeetCode's follow-up asks for more: use only O(1) extra memory.
Worked Examples
matrix = [[1,1,1],[1,0,1],[1,1,1]][[1,0,1],[0,0,0],[1,0,1]]0 sits in the middle, so the middle row and the middle column become 0. The four corners keep their 1.matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]][[0,0,0,0],[0,4,5,0],[0,3,1,0]]0. The middle cells 4, 5, 3, 1 keep their values. This is the trap case: row 0 has zeros of its own, so it must be cleared, but only after the second pass has read the column flags in it.⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Core Insight
Every flag lives in a cell that ends up 0 anyway, so row 0 and column 0 can store the flags without losing any value that is still needed. The only information the flags overwrite is whether row 0 and column 0 had zeros of their own, and two booleans recorded first keep it.
Real-World Scenario & Production Applications
A spreadsheet engine or an image tool that must blank out every row and column touched by a bad reading, on a large grid already in memory, where a second grid (or even a mask per row and column on a small device) is not affordable: the grid's own cells hold the bookkeeping.
Step-by-Step Execution Trace Table
Example 2 (the trap case: row 0 has zeros of its own), matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]:
| Step | Line | Result | Why |
|---|---|---|---|
| 1 | first_row_zero = any(...) | True | Row 0 has a 0 at columns 0 and 3; recorded before any flag goes into row 0 |
| 2 | first_col_zero = any(...) | True | Column 0 has a 0 in row 0 |
| 3 | Pass 1 over rows 1-2, columns 1-3 | no flag written | No inner cell is 0; the 0 already at matrix[0][3] works as column 3's flag |
| 4 | Pass 2, r = 1 | [3, 4, 5, 0] | Only matrix[0][3] == 0, so only matrix[1][3] becomes 0 |
| 5 | Pass 2, r = 2 | [1, 3, 1, 0] | Same: column 3's flag |
| 6 | if first_row_zero: | row 0 = [0, 0, 0, 0] | Cleared now, after pass 2 has read every flag in it |
| 7 | if first_col_zero: | column 0 = [0, 0, 0] | Result: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] |
Clearing row 0 before pass 2 would make every matrix[0][c] == 0 true, and pass 2 would zero the whole grid.
| 1 | Every cell of a row or column that holds a zero ends up `0`, so those cells can store the marks without losing any value that is still needed: row 0 flags the columns and column 0 flags the rows. |
| 2 | Keep this true: before pass 2, `matrix[r][0] == 0` means row `r` held a zero and `matrix[0][c] == 0` means column `c` did, while `first_row_zero` and `first_col_zero` keep row 0's and column 0's own answers. |
| 3 | Record the two booleans; pass 1 over `range(1, m)` and `range(1, n)` writes `matrix[r][0] = 0` and `matrix[0][c] = 0` for each zero; pass 2 zeroes `matrix[r][c]` when either flag is `0`; finally clear row 0 and column 0 if their booleans say so. |
| 4 | The trap: compute `first_row_zero` and `first_col_zero` before pass 1, and clear row 0 and column 0 after pass 2. Clearing them first turns every flag to `0` and wipes the whole grid. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The easy answer copies the grid, or keeps one marker per row and per column, and zeroes from those. With no extra memory allowed, the marks need a home inside matrix itself. In-Place Marking looks for cells whose final value is already known: a zero at (r, c) means row r and column c end up all zero, so the first cell of that row, matrix[r][0], and the top cell of that column, matrix[0][c], can hold the marks without losing anything. Pass 1 writes the flags and pass 2 reads them. The only thing the flags overwrite is row 0's and column 0's own information, so two booleans, first_row_zero and first_col_zero, save it before pass 1 and are used last.
🗂️ The Analogy: Sticky Notes on the Edge of the Chart
A teacher must wipe every row and every column of a big wall chart that contains a missing score, and she has no notebook to write in. So she puts a red sticky note on the first square of each affected row and on the top square of each affected column: those squares get wiped anyway. Then she walks the chart again and wipes every square whose row or column has a red note. The top row and the left column carry the notes, so before sticking any note on them she remembers whether they had a missing score of their own, and she wipes them last, once nobody needs their notes.
🔑 Why It Works
Every cell a flag overwrites is a cell the answer sets to 0 anyway, so writing a flag never destroys a value you still need. The first row's and first column's own zeros are the exception, which is why the two booleans are read before any flag is written. Both passes skip row 0 and column 0 (range(1, m), range(1, n)), and row 0 and column 0 are cleared only after pass 2 has read every flag.
Recording row 0 and column 0 too late:
first_row_zeroandfirst_col_zeromust be computed before pass 1 writes any flag. Computed after, a column flag in row 0 looks like an original zero: on[[1,1,1],[1,0,1],[1,1,1]]the whole first row would be wiped.Clearing row 0 or column 0 too early: clear them after pass 2. On
[[0,1,2,0],[3,4,5,2],[1,3,1,5]], clearing row 0 first makes everymatrix[0][c] == 0true, and pass 2 zeroes the whole grid instead of keeping4, 5, 3, 1.One flag for the corner:
matrix[0][0]belongs to row 0 and to column 0, so it can't flag both. A zero only in column 0, as in[[1,2],[0,4]], must not wipe row 0's2; two booleans keep the two answers apart.Passes that include row 0 or column 0: both passes run over
range(1, m)andrange(1, n). A pass 2 that starts at row 0 zeroes row 0 (whenmatrix[0][0] == 0) while later rows still read it as their column flags.Zeroing on sight: writing zeros across row
rand columncas soon asmatrix[r][c] == 0is found makes later cells read those new zeros as original ones, and the zeros spread until most of the grid is0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"wipes out its whole row and its whole column", "in place", and the follow-up "O(1) extra memory": a change that depends on the grid as it was, with no memory for a copy or for one marker per row and column. That is the signal for In-Place Marking: find cells whose final value is already known and keep the marks there.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Before pass 2, matrix[r][0] == 0 exactly when row r (for r >= 1) held a zero, and matrix[0][c] == 0 exactly when column c (for c >= 1) held a zero; first_row_zero and first_col_zero keep row 0's and column 0's own answers. Pass 2 zeroes matrix[r][c] when matrix[r][0] == 0 or matrix[0][c] == 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use In-Place Marking: keep the bookkeeping in cells of the input whose final value I already know. A zero at row r, column c means that whole row and that whole column end up zero, so the first cell of row r and the top cell of column c can hold the flags without losing any value that is still needed. Pass one scans the inner cells and writes those flags; pass two zeroes every inner cell whose row flag or column flag is zero. The catch is that row zero and column zero are real data too. So before writing any flag I record two booleans, whether row zero and whether column zero had a zero of their own, and I clear them last, after pass two has read every flag; clearing them first would wipe the whole grid. That's O(M times N) time and
O(1)extra space.
Complexity & Mathematical Proof
O(M * N)
Count the work line by line. first_row_zero reads the N cells of row 0 and first_col_zero the M cells of column 0. Pass 1 and pass 2 each visit the (M - 1) * (N - 1) inner cells once, with O(1) work per cell: one test and at most two writes. Clearing row 0 and column 0 at the end touches at most N + M cells. The total is at most 2(M + N) + 2(M - 1)(N - 1) steps, which is O(M * N).
O(1)
The flags are written into matrix itself, which the problem hands us and changes in place anyway. The extra memory is m, n, the loop indices r and c, and the two booleans first_row_zero and first_col_zero: O(1). A copy of the grid would cost O(M * N), and one marker per row and per column O(M + N).
T(M, N) = (M + N) + 2 · (M - 1)(N - 1) + (M + N) = O(M · N)
Derivation Progression
O(M + N)
any(...) over the N cells of row 0 and the M cells of column 0.
O((M - 1)(N - 1))
Each inner cell: one test matrix[r][c] == 0, and at most two flag writes.
O((M - 1)(N - 1))
Each inner cell: one test of its two flags, and at most one write.
O(M + N)
At most N writes for row 0 and M for column 0.
O(M · N)
Two passes over the grid plus its first row and first column.
Variable Definitions
Number of rows, len(matrix) (at most 200)
Number of columns, len(matrix[0]) (at most 200)
Memory Architecture & Bounds
O(1) No recursion
O(1): first_row_zero, first_col_zero, m, n, r, c; the flags live in matrix
O(1): nothing is returned, matrix is changed in place
Boundary Best / Worst Cases
: every cell is read even when the grid has no zero
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "wipes out its whole row and its whole column", "in place", "O(1) extra memory" (the follow-up). A change that depends on the grid as it was, with no memory for a copy: In-Place Marking, keep the marks in cells whose final value is already known.
Up to cells with values in . Two passes are about cell visits. A copy of the grid costs extra memory and one marker per row and column ; flags in row 0 and column 0 cost .
If a very large grid is processed in horizontal stripes by several workers, row 0 and column 0 become shared state: every worker must finish pass 1 before any worker starts pass 2, and the first row and column are cleared only after the last stripe of pass 2. Values span the whole 32-bit range, so a sentinel such as -1 in place of the flags could collide with real data; writing 0 never does, because those cells end up 0.