Set Matrix Zeroes (LeetCode 73)
You will see how row 0 and column 0 of the matrix can hold every flag the job needs, so no extra memory is used.
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]]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]]⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Why It Works & Core Invariant
Every flag lives in a cell that ends up 0 anyway, so row 0 and column 0 can store the flags for free. 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.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []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 for free: 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. |
Target: Set Matrix Zeroes (LeetCode 73). Row 0 and column 0 are about to hold flags, so their own zeros are recorded first, in two booleans.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
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.
🪄 The Mathematical Harmony / Magic Trick
first_row_zero = any(matrix[0][c] == 0 for c in range(n))first_col_zero = any(matrix[r][0] == 0 for r in range(m))for r in range(1, m): for c in range(1, n): if matrix[r][c] == 0: matrix[r][0] = 0 matrix[0][c] = 0 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.
💡 Summary
Record first_row_zero and first_col_zero, flag with matrix[r][0] = 0 and matrix[0][c] = 0 in pass 1, zero every inner cell whose flag is set in pass 2, then clear row 0 and column 0 last. time, extra space.
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
You will see how a senior engineer turns "constant extra space" into "store the flags in cells that end up zero anyway" and says so out loud.
Pattern Recognition Signals
The 10-second spot
"Set its entire row and column to 0", "in place", and the follow-up "can you use constant extra space?": 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
Record
first_row_zeroandfirst_col_zerobefore pass 1, and clear row 0 and column 0 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 zeroes the whole grid; computingfirst_row_zeroafter pass 1 mistakes a column flag for an original zero.Two booleans, not one
matrix[0][0]flag: with a zero only in column 0, as in[[1,2],[0,4]], one shared flag would also wipe row 0's2.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.Mark first, zero later: zeroing row
rand columncthe momentmatrix[r][c] == 0is found makes the rest of the scan read those new zeros as original ones.
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 for free. 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.
So: row 0 and column 0 hold the flags, first_row_zero and first_col_zero are recorded first, and row 0 and column 0 are cleared last.
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)
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).
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: "set its entire row and column to 0", "in place", "constant space" (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 .
Clearing row 0 or column 0 before pass 2, or computing the booleans after pass 1, wipes rows and columns that had no zero. 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.
Core Algorithmic State Invariants
A zero at `(r, c)` is recorded as `matrix[r][0] = 0` and `matrix[0][c] = 0`. Both cells become `0` in the answer anyway, so the flags cost no memory and lose no information.
`first_row_zero` and `first_col_zero` are computed before pass 1 writes any flag, and row 0 and column 0 are cleared only after pass 2 has read the flags. Either order reversed wipes rows or columns that had no zero.
Pass 1 marks and pass 2 reads, each over the inner cells once: O(M * N) time, and O(1) extra memory beyond the grid itself.
Set Matrix Zeroes (LeetCode 73)
You will see how row 0 and column 0 of the matrix can hold every flag the job needs, so no extra memory is used.
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]]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]]⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
Why It Works & Core Invariant
Every flag lives in a cell that ends up 0 anyway, so row 0 and column 0 can store the flags for free. 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.
Subproblems & Recurrence Decomposition3 Phases
Establish 4-wall perimeter bounding (top, bottom, left, right) or binary exponent halving state x^n = (x^2)^(n/2).
top, bottom = 0, R - 1
left, right = 0, C - 1
res = []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 for free: 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. |
Target: Set Matrix Zeroes (LeetCode 73). Row 0 and column 0 are about to hold flags, so their own zeros are recorded first, in two booleans.
Boundary pointers contract inward after each directional sweep; modular arithmetic bounds state cyclically.
while top <= bottom and left <= right: sweep right, down, left, up, contracting respective pointer.
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.
🪄 The Mathematical Harmony / Magic Trick
first_row_zero = any(matrix[0][c] == 0 for c in range(n))first_col_zero = any(matrix[r][0] == 0 for r in range(m))for r in range(1, m): for c in range(1, n): if matrix[r][c] == 0: matrix[r][0] = 0 matrix[0][c] = 0 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.
💡 Summary
Record first_row_zero and first_col_zero, flag with matrix[r][0] = 0 and matrix[0][c] = 0 in pass 1, zero every inner cell whose flag is set in pass 2, then clear row 0 and column 0 last. time, extra space.
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
You will see how a senior engineer turns "constant extra space" into "store the flags in cells that end up zero anyway" and says so out loud.
Pattern Recognition Signals
The 10-second spot
"Set its entire row and column to 0", "in place", and the follow-up "can you use constant extra space?": 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
Record
first_row_zeroandfirst_col_zerobefore pass 1, and clear row 0 and column 0 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 zeroes the whole grid; computingfirst_row_zeroafter pass 1 mistakes a column flag for an original zero.Two booleans, not one
matrix[0][0]flag: with a zero only in column 0, as in[[1,2],[0,4]], one shared flag would also wipe row 0's2.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.Mark first, zero later: zeroing row
rand columncthe momentmatrix[r][c] == 0is found makes the rest of the scan read those new zeros as original ones.
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 for free. 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.
So: row 0 and column 0 hold the flags, first_row_zero and first_col_zero are recorded first, and row 0 and column 0 are cleared last.
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)
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).
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: "set its entire row and column to 0", "in place", "constant space" (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 .
Clearing row 0 or column 0 before pass 2, or computing the booleans after pass 1, wipes rows and columns that had no zero. 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.
Core Algorithmic State Invariants
A zero at `(r, c)` is recorded as `matrix[r][0] = 0` and `matrix[0][c] = 0`. Both cells become `0` in the answer anyway, so the flags cost no memory and lose no information.
`first_row_zero` and `first_col_zero` are computed before pass 1 writes any flag, and row 0 and column 0 are cleared only after pass 2 has read the flags. Either order reversed wipes rows or columns that had no zero.
Pass 1 marks and pass 2 reads, each over the inner cells once: O(M * N) time, and O(1) extra memory beyond the grid itself.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Save what the flag cells hold before they become flags | first_row_zero = any(matrix[0][c] == 0 for c in range(n))
first_col_zero = any(matrix[r][0] == 0 for r in range(m)) | Row 0 and column 0 are about to hold flags, so their own zeros are recorded first, in two booleans. |
| Scan only the cells the flags describe | for r in range(1, m):
for c in range(1, n): | Both passes skip row 0 and column 0: those cells are the flags, not the data being flagged. |
| Write the mark into a cell whose final value is known | matrix[r][0] = 0
matrix[0][c] = 0 | A zero at `(r, c)` means row `r` and column `c` end up all zero, so their first cells can carry the flags without losing anything. |
| Second pass: act on the marks | if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0 | An inner cell becomes `0` when its row flag or its column flag is set. |
| Clear the flag cells last | if first_row_zero:
for c in range(n):
matrix[0][c] = 0 | Only now, after pass 2 has read every column flag, may row 0 be cleared. |
| Clear the flag cells last | if first_col_zero:
for r in range(m):
matrix[r][0] = 0 | The same for column 0 and its row flags. |