In-Place Markers (First Row/Column Flags, Two States per Cell)
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.
0 sits in the middle, so the middle row and the middle column become 0. The four corners keep their 1.In-Place Marking
matrix ➔ markers in the first row / column or spare bits ➔ apply in a second passO(1) extra memory, but each change depends on the input as it was: rows or columns to wipe, or a new state that every neighbour must still read in its old form.| 1 | def set_zeroes(matrix: list[list[int]]) -> None: |
| 2 | """Set Matrix Zeroes: row 0 and column 0 hold the flags for the other rows and columns. |
| 3 | Time: O(M * N) | Space: O(1) |
| 4 | """ |
| 5 | m, n = len(matrix), len(matrix[0]) |
| 6 | |
| 7 | # 1. Save Row 0's and Column 0's Own Zeros First: |
| 8 | # Pass 1 below overwrites row 0 and column 0 with flags, so whether |
| 9 | # they originally held a zero must be recorded before any flag is written. |
| 10 | first_row_zero = any(matrix[0][c] == 0 for c in range(n)) |
| 11 | first_col_zero = any(matrix[r][0] == 0 for r in range(m)) |
| 12 | |
| 13 | # 2. Mark Flags in Row 0 and Column 0: |
| 14 | # A zero found inside the matrix (outside row 0 and column 0) means its |
| 15 | # whole row and column end up zero, so that is recorded by zeroing the |
| 16 | # row's cell in column 0 and the column's cell in row 0. |
| 17 | for r in range(1, m): |
| 18 | for c in range(1, n): |
| 19 | if matrix[r][c] == 0: |
| 20 | matrix[r][0] = 0 |
| 21 | matrix[0][c] = 0 |
| 22 | |
| 23 | # 3. Apply the Flags to Every Inner Cell: |
| 24 | # Any inner cell whose row flag or column flag is set is zeroed; row 0 |
| 25 | # and column 0 themselves are skipped here because they still need to be read. |
| 26 | for r in range(1, m): |
| 27 | for c in range(1, n): |
| 28 | if matrix[r][0] == 0 or matrix[0][c] == 0: |
| 29 | matrix[r][c] = 0 |
| 30 | |
| 31 | # 4. Clear Row 0 and Column 0 Last: |
| 32 | # Row 0 and column 0 are cleared only after every other cell has read |
| 33 | # their flags; clearing them earlier would turn every flag true and wipe the whole matrix. |
| 34 | if first_row_zero: |
| 35 | for c in range(n): |
| 36 | matrix[0][c] = 0 |
| 37 | if first_col_zero: |
| 38 | for r in range(m): |
| 39 | matrix[r][0] = 0 |
first_row_zero / first_col_zero hold row 0's and column 0's own answers from before any flag was written.When no extra memory is allowed, store the marks in cells whose final value you already know: a zero at (r, c) means row r and column c end up all zero, so pass 1 writes the flags matrix[r][0] = 0 and matrix[0][c] = 0, and pass 2 zeroes every cell whose row flag or column flag is 0. Writing a flag loses nothing, because both flag cells become zero in the answer anyway; the same idea packs two states into one cell when every neighbour must still read it in its old form, because the old value stays readable until every reader is done, whether that means a whole cell repurposed as a flag or one bit of it holding the next state. The trap is that row 0 and column 0 are data as well as flags: compute first_row_zero and first_col_zero before pass 1 writes any flag, keep both passes to r >= 1 and c >= 1, and clear row 0 and column 0 last, because clearing them first turns every flag to 0 and wipes the whole matrix.
See it run
In-Place Marking, step by step
pass startfirst_row_zero falsefirst_col_zero false
Each box is one cell of the matrix. Row 0 and column 0 hold the flags for the other rows and columns.
scanthe inner cell the loop is checkingset 0a cell the code writes as 0 in this stepflaga cell in row 0 or column 0 that holds a markkeepsa cell that must stay unchangedsavedan original 0 in row 0 or column 0, recorded in first_row_zero or first_col_zero
Start: a 3 by 4 matrix. Row 0 and column 0 will hold the flags, so their own zeros are saved first.
Gotcha 1 of 5
- The trap
Gotcha 1: Clearing row 0 before pass 2 reads the flags
Mistakeif first_row_zero: for c in range(n): matrix[0][c] = 0 for r in range(1, m): for c in range(1, n): if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0Fixfor r in range(1, m): for c in range(1, n): if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0 if first_row_zero: for c in range(n): matrix[0][c] = 0What happens: After pass 1, row 0 holds the column flags. A 0 at
matrix[0][c]means "clear columnc". If row 0 is cleared before pass 2, everymatrix[0][c]becomes 0. Pass 2 then finds a flag in every column and clears the whole matrix.Example: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]Mistake: returns [[0, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[0, 0, 0], [0, 4, 5], [0, 7, 8]]
- The values are 1..n and each belongs in its own slot, as in First Missing Positive (LC 41): once a value is home, its old slot content is never needed again, so no mark has to keep the old value readable. See Cyclic Sort
Deep Dive
Why a flag in row 0 or column 0 loses nothing
Set Matrix Zeroes (LC 73) needs to remember which rows and columns contain a 0. The simple way stores two lists, one for the rows and one for the columns, which costs O(M + N) extra space. The card stores the same information inside the matrix, so the extra space is O(1).
A flag must be written in a cell whose final value is already known. If matrix[r][c] is 0, then row r and column c end up all 0. So matrix[r][0] and matrix[0][c] end up 0 in the answer. Writing a 0 there as a flag changes no final value.
The flag still destroys the old value of that cell. This matters only for the zeros that were already in row 0 and column 0. A 0 at matrix[r][0] with r >= 1 already acts as the flag for row r. It also means that column 0 must be cleared, and one boolean records that: first_col_zero. A 0 in row 0 is handled in the same way by first_row_zero. That is why both booleans are computed before pass 1.
The two passes, traced on a 3 by 4 matrix
Take matrix = [[1, 0, 3, 4], [5, 6, 7, 8], [9, 10, 11, 0]]. Row 0 holds a 0 at matrix[0][1], so first_row_zero is True. Column 0 holds no 0, so first_col_zero is False.
Pass 1 checks the six cells with r >= 1 and c >= 1. Only matrix[2][3] is 0. It writes matrix[2][0] = 0 and matrix[0][3] = 0. The matrix is now [[1, 0, 3, 0], [5, 6, 7, 8], [0, 10, 11, 0]].
Pass 2 checks the same six cells. A cell becomes 0 when matrix[r][0] == 0 or matrix[0][c] == 0. matrix[1][2] = 7 has the flags 5 and 3, so it stays. The other five cells change to 0 or already are 0.
The last step clears row 0, because first_row_zero is True. Column 0 keeps its values, because first_col_zero is False. The result is [[0, 0, 0, 0], [5, 0, 7, 0], [0, 0, 0, 0]].
Why row 0 and column 0 are cleared last
After pass 1, row 0 holds the column flags and column 0 holds the row flags. Pass 2 reads them, so they must keep their flag values until pass 2 ends.
Suppose row 0 is cleared first. Every matrix[0][c] becomes 0, and pass 2 sees a flag for every column. It clears every cell. In the example above, matrix[1][2] = 7 would be lost, although it must stay.
For the same reason, pass 2 starts at r = 1 and c = 1. Row 0 and column 0 are never changed by pass 2. They are cleared in the last step, when no cell needs to read them any more.
The two booleans must be computed before pass 1. After pass 1, a 0 in row 0 can be an original value or a flag, and nothing tells them apart.
Two states in one cell: Game of Life (LC 289)
Game of Life (LC 289) has the same difficulty. Every cell must read the old state of its neighbours, but the new state is written in the same grid.
The card's idea gives the solution. Each cell holds two states, the old state in bit 0 and the new state in bit 1. While scanning, read a neighbour as board[r][c] & 1, which is its old state. Write the new state with board[r][c] |= next << 1. After the scan, board[r][c] >>= 1 makes the new state the only state.
Example: a vertical row of three live cells [[0, 1, 0], [0, 1, 0], [0, 1, 0]] becomes the horizontal row [[0, 0, 0], [1, 1, 1], [0, 0, 0]].
In both problems, the old value stays readable until every reader is done. The cost is O(M * N) time and O(1) extra space.
60-Second Pitch
"The simple solution keeps two lists of rows and columns that hold a 0. That costs O(M + N) space. I store those marks inside the matrix instead. A 0 at matrix[r][c] means row r and column c will be all 0, so I write a 0 into matrix[r][0] and matrix[0][c]. Those two cells end as 0 anyway, so the flag loses no final value. Row 0 and column 0 are also data, so I save their own answers in two booleans before I write any flag. Pass 2 zeroes the inner cells from the flags, and I clear row 0 and column 0 last. The time is O(M * N) and the extra space is O(1). The same idea of two states in one cell solves Game of Life."
Common Questions
- Why can a flag be written into row 0 and column 0 without losing data?
A 0 at
matrix[r][c]means rowrand columncend up all 0. Somatrix[r][0]andmatrix[0][c]are 0 in the answer. The only information in those cells that is still needed is whether row 0 or column 0 held a 0 at the start. Two booleans store that before any flag is written.- Why do you need two booleans and not one?
One boolean cannot tell whether the 0 was in row 0 or in column 0. If the 0 was only in column 0, one shared flag would also clear row 0, which is wrong. Using
matrix[0][0]as the shared flag has the same problem, because that cell belongs to both.- Why does pass 2 start at row 1 and column 1, and why is row 0 cleared last?
Row 0 and column 0 hold the flags, and pass 2 reads them. If pass 2 or an earlier step changed them, other cells would read false flags. Clearing them last means every inner cell has already read its flags.
- What is the time and space complexity, and how does it compare with two lists?
The time is O(M * N), because each pass visits each cell once. The extra space is
O(1), which is two booleans. The two-list solution has the same time and O(M + N) space.- How does the same idea solve Game of Life (LC 289) in place?
Each cell stores the old state in bit 0 and the new state in bit 1. Neighbours are read with
& 1, so they still see the old state. The new state is written with|= next << 1. A final pass with>>= 1keeps only the new state.
SWE Reasoning
Spot it
- The matrix must be changed in place, and the extra memory must be
O(1). - Each change depends on the matrix as it was, such as wiping rows and columns that hold a 0 (Set Matrix Zeroes (LC 73)).
- Every cell must read the old state of its neighbours before its own new state is stored (Game of Life (LC 289)).
- A cell has a known final value, so it can hold a mark first and the value later.
The invariant, step by step
first_row_zeroandfirst_col_zeroare computed before anything is changed. They hold the answers of row 0 and column 0 for the original matrix.- Pass 1 visits only cells with
r >= 1andc >= 1. For each 0, it writes 0 intomatrix[r][0]andmatrix[0][c]. - Those two cells end up 0 in the answer. So a flag never changes a final value.
- Pass 2 visits the same inner cells. A cell becomes 0 when its row flag or its column flag is 0. Row 0 and column 0 are not changed yet, so every flag is still readable.
- The last step clears row 0 and column 0 when the saved booleans say so.
- Now every row and every column that held a 0 is all 0, and no other cell changed.
Traps
- Clearing row 0 before pass 2. Every column flag becomes 0, and pass 2 clears the whole matrix. For
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]the result is all zeros instead of[[0, 0, 0], [0, 4, 5], [0, 7, 8]]. - Computing
first_row_zeroafter pass 1. A flag written into row 0 looks like an original 0. Row 0 is then cleared although it had no 0. - One boolean for both. The boolean says that row 0 or column 0 had a 0, but not which one. A 0 only in column 0 would also clear row 0.
- Zeroing the row and column during the scan. The scan meets the new zeros later and takes them for original zeros. The zeros spread to rows and columns that had none.
- Starting pass 2 at row 0. If
matrix[0][0]is 0, pass 2 sets everymatrix[0][c]to 0, which makes false flags for every column.
Practice
In-Place Markers (First Row/Column Flags, Two States per Cell)
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.
0 sits in the middle, so the middle row and the middle column become 0. The four corners keep their 1.In-Place Marking
matrix ➔ markers in the first row / column or spare bits ➔ apply in a second passO(1) extra memory, but each change depends on the input as it was: rows or columns to wipe, or a new state that every neighbour must still read in its old form.| 1 | def set_zeroes(matrix: list[list[int]]) -> None: |
| 2 | """Set Matrix Zeroes: row 0 and column 0 hold the flags for the other rows and columns. |
| 3 | Time: O(M * N) | Space: O(1) |
| 4 | """ |
| 5 | m, n = len(matrix), len(matrix[0]) |
| 6 | |
| 7 | # 1. Save Row 0's and Column 0's Own Zeros First: |
| 8 | # Pass 1 below overwrites row 0 and column 0 with flags, so whether |
| 9 | # they originally held a zero must be recorded before any flag is written. |
| 10 | first_row_zero = any(matrix[0][c] == 0 for c in range(n)) |
| 11 | first_col_zero = any(matrix[r][0] == 0 for r in range(m)) |
| 12 | |
| 13 | # 2. Mark Flags in Row 0 and Column 0: |
| 14 | # A zero found inside the matrix (outside row 0 and column 0) means its |
| 15 | # whole row and column end up zero, so that is recorded by zeroing the |
| 16 | # row's cell in column 0 and the column's cell in row 0. |
| 17 | for r in range(1, m): |
| 18 | for c in range(1, n): |
| 19 | if matrix[r][c] == 0: |
| 20 | matrix[r][0] = 0 |
| 21 | matrix[0][c] = 0 |
| 22 | |
| 23 | # 3. Apply the Flags to Every Inner Cell: |
| 24 | # Any inner cell whose row flag or column flag is set is zeroed; row 0 |
| 25 | # and column 0 themselves are skipped here because they still need to be read. |
| 26 | for r in range(1, m): |
| 27 | for c in range(1, n): |
| 28 | if matrix[r][0] == 0 or matrix[0][c] == 0: |
| 29 | matrix[r][c] = 0 |
| 30 | |
| 31 | # 4. Clear Row 0 and Column 0 Last: |
| 32 | # Row 0 and column 0 are cleared only after every other cell has read |
| 33 | # their flags; clearing them earlier would turn every flag true and wipe the whole matrix. |
| 34 | if first_row_zero: |
| 35 | for c in range(n): |
| 36 | matrix[0][c] = 0 |
| 37 | if first_col_zero: |
| 38 | for r in range(m): |
| 39 | matrix[r][0] = 0 |
first_row_zero / first_col_zero hold row 0's and column 0's own answers from before any flag was written.When no extra memory is allowed, store the marks in cells whose final value you already know: a zero at (r, c) means row r and column c end up all zero, so pass 1 writes the flags matrix[r][0] = 0 and matrix[0][c] = 0, and pass 2 zeroes every cell whose row flag or column flag is 0. Writing a flag loses nothing, because both flag cells become zero in the answer anyway; the same idea packs two states into one cell when every neighbour must still read it in its old form, because the old value stays readable until every reader is done, whether that means a whole cell repurposed as a flag or one bit of it holding the next state. The trap is that row 0 and column 0 are data as well as flags: compute first_row_zero and first_col_zero before pass 1 writes any flag, keep both passes to r >= 1 and c >= 1, and clear row 0 and column 0 last, because clearing them first turns every flag to 0 and wipes the whole matrix.
See it run
In-Place Marking, step by step
pass startfirst_row_zero falsefirst_col_zero false
Each box is one cell of the matrix. Row 0 and column 0 hold the flags for the other rows and columns.
scanthe inner cell the loop is checkingset 0a cell the code writes as 0 in this stepflaga cell in row 0 or column 0 that holds a markkeepsa cell that must stay unchangedsavedan original 0 in row 0 or column 0, recorded in first_row_zero or first_col_zero
Start: a 3 by 4 matrix. Row 0 and column 0 will hold the flags, so their own zeros are saved first.
Gotcha 1 of 5
- The trap
Gotcha 1: Clearing row 0 before pass 2 reads the flags
Mistakeif first_row_zero: for c in range(n): matrix[0][c] = 0 for r in range(1, m): for c in range(1, n): if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0Fixfor r in range(1, m): for c in range(1, n): if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0 if first_row_zero: for c in range(n): matrix[0][c] = 0What happens: After pass 1, row 0 holds the column flags. A 0 at
matrix[0][c]means "clear columnc". If row 0 is cleared before pass 2, everymatrix[0][c]becomes 0. Pass 2 then finds a flag in every column and clears the whole matrix.Example: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]Mistake: returns [[0, 0, 0], [0, 0, 0], [0, 0, 0]]Fix: returns [[0, 0, 0], [0, 4, 5], [0, 7, 8]]
- The values are 1..n and each belongs in its own slot, as in First Missing Positive (LC 41): once a value is home, its old slot content is never needed again, so no mark has to keep the old value readable. See Cyclic Sort
Deep Dive
Why a flag in row 0 or column 0 loses nothing
Set Matrix Zeroes (LC 73) needs to remember which rows and columns contain a 0. The simple way stores two lists, one for the rows and one for the columns, which costs O(M + N) extra space. The card stores the same information inside the matrix, so the extra space is O(1).
A flag must be written in a cell whose final value is already known. If matrix[r][c] is 0, then row r and column c end up all 0. So matrix[r][0] and matrix[0][c] end up 0 in the answer. Writing a 0 there as a flag changes no final value.
The flag still destroys the old value of that cell. This matters only for the zeros that were already in row 0 and column 0. A 0 at matrix[r][0] with r >= 1 already acts as the flag for row r. It also means that column 0 must be cleared, and one boolean records that: first_col_zero. A 0 in row 0 is handled in the same way by first_row_zero. That is why both booleans are computed before pass 1.
The two passes, traced on a 3 by 4 matrix
Take matrix = [[1, 0, 3, 4], [5, 6, 7, 8], [9, 10, 11, 0]]. Row 0 holds a 0 at matrix[0][1], so first_row_zero is True. Column 0 holds no 0, so first_col_zero is False.
Pass 1 checks the six cells with r >= 1 and c >= 1. Only matrix[2][3] is 0. It writes matrix[2][0] = 0 and matrix[0][3] = 0. The matrix is now [[1, 0, 3, 0], [5, 6, 7, 8], [0, 10, 11, 0]].
Pass 2 checks the same six cells. A cell becomes 0 when matrix[r][0] == 0 or matrix[0][c] == 0. matrix[1][2] = 7 has the flags 5 and 3, so it stays. The other five cells change to 0 or already are 0.
The last step clears row 0, because first_row_zero is True. Column 0 keeps its values, because first_col_zero is False. The result is [[0, 0, 0, 0], [5, 0, 7, 0], [0, 0, 0, 0]].
Why row 0 and column 0 are cleared last
After pass 1, row 0 holds the column flags and column 0 holds the row flags. Pass 2 reads them, so they must keep their flag values until pass 2 ends.
Suppose row 0 is cleared first. Every matrix[0][c] becomes 0, and pass 2 sees a flag for every column. It clears every cell. In the example above, matrix[1][2] = 7 would be lost, although it must stay.
For the same reason, pass 2 starts at r = 1 and c = 1. Row 0 and column 0 are never changed by pass 2. They are cleared in the last step, when no cell needs to read them any more.
The two booleans must be computed before pass 1. After pass 1, a 0 in row 0 can be an original value or a flag, and nothing tells them apart.
Two states in one cell: Game of Life (LC 289)
Game of Life (LC 289) has the same difficulty. Every cell must read the old state of its neighbours, but the new state is written in the same grid.
The card's idea gives the solution. Each cell holds two states, the old state in bit 0 and the new state in bit 1. While scanning, read a neighbour as board[r][c] & 1, which is its old state. Write the new state with board[r][c] |= next << 1. After the scan, board[r][c] >>= 1 makes the new state the only state.
Example: a vertical row of three live cells [[0, 1, 0], [0, 1, 0], [0, 1, 0]] becomes the horizontal row [[0, 0, 0], [1, 1, 1], [0, 0, 0]].
In both problems, the old value stays readable until every reader is done. The cost is O(M * N) time and O(1) extra space.
60-Second Pitch
"The simple solution keeps two lists of rows and columns that hold a 0. That costs O(M + N) space. I store those marks inside the matrix instead. A 0 at matrix[r][c] means row r and column c will be all 0, so I write a 0 into matrix[r][0] and matrix[0][c]. Those two cells end as 0 anyway, so the flag loses no final value. Row 0 and column 0 are also data, so I save their own answers in two booleans before I write any flag. Pass 2 zeroes the inner cells from the flags, and I clear row 0 and column 0 last. The time is O(M * N) and the extra space is O(1). The same idea of two states in one cell solves Game of Life."
Common Questions
- Why can a flag be written into row 0 and column 0 without losing data?
A 0 at
matrix[r][c]means rowrand columncend up all 0. Somatrix[r][0]andmatrix[0][c]are 0 in the answer. The only information in those cells that is still needed is whether row 0 or column 0 held a 0 at the start. Two booleans store that before any flag is written.- Why do you need two booleans and not one?
One boolean cannot tell whether the 0 was in row 0 or in column 0. If the 0 was only in column 0, one shared flag would also clear row 0, which is wrong. Using
matrix[0][0]as the shared flag has the same problem, because that cell belongs to both.- Why does pass 2 start at row 1 and column 1, and why is row 0 cleared last?
Row 0 and column 0 hold the flags, and pass 2 reads them. If pass 2 or an earlier step changed them, other cells would read false flags. Clearing them last means every inner cell has already read its flags.
- What is the time and space complexity, and how does it compare with two lists?
The time is O(M * N), because each pass visits each cell once. The extra space is
O(1), which is two booleans. The two-list solution has the same time and O(M + N) space.- How does the same idea solve Game of Life (LC 289) in place?
Each cell stores the old state in bit 0 and the new state in bit 1. Neighbours are read with
& 1, so they still see the old state. The new state is written with|= next << 1. A final pass with>>= 1keeps only the new state.
SWE Reasoning
Spot it
- The matrix must be changed in place, and the extra memory must be
O(1). - Each change depends on the matrix as it was, such as wiping rows and columns that hold a 0 (Set Matrix Zeroes (LC 73)).
- Every cell must read the old state of its neighbours before its own new state is stored (Game of Life (LC 289)).
- A cell has a known final value, so it can hold a mark first and the value later.
The invariant, step by step
first_row_zeroandfirst_col_zeroare computed before anything is changed. They hold the answers of row 0 and column 0 for the original matrix.- Pass 1 visits only cells with
r >= 1andc >= 1. For each 0, it writes 0 intomatrix[r][0]andmatrix[0][c]. - Those two cells end up 0 in the answer. So a flag never changes a final value.
- Pass 2 visits the same inner cells. A cell becomes 0 when its row flag or its column flag is 0. Row 0 and column 0 are not changed yet, so every flag is still readable.
- The last step clears row 0 and column 0 when the saved booleans say so.
- Now every row and every column that held a 0 is all 0, and no other cell changed.
Traps
- Clearing row 0 before pass 2. Every column flag becomes 0, and pass 2 clears the whole matrix. For
[[0, 1, 2], [3, 4, 5], [6, 7, 8]]the result is all zeros instead of[[0, 0, 0], [0, 4, 5], [0, 7, 8]]. - Computing
first_row_zeroafter pass 1. A flag written into row 0 looks like an original 0. Row 0 is then cleared although it had no 0. - One boolean for both. The boolean says that row 0 or column 0 had a 0, but not which one. A 0 only in column 0 would also clear row 0.
- Zeroing the row and column during the scan. The scan meets the new zeros later and takes them for original zeros. The zeros spread to rows and columns that had none.
- Starting pass 2 at row 0. If
matrix[0][0]is 0, pass 2 sets everymatrix[0][c]to 0, which makes false flags for every column.