Given an m × n matrix, if a cell is 0, set its entire row and column to 0 — in place.
Example
Input matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output [[1,0,1],[0,0,0],[1,0,1]]
Key Pointers
Don't zero cells the moment you find a zero — that cascades, since a newly-zeroed cell would trigger zeroing its own row/column on a later check.
Record which rows and columns need zeroing first, in a single pass, then apply all of it in a second pass.
Two sets (zero rows, zero columns) keep this at O(m + n) space — simple to reason about, and enough unless true O(1) space is required.
Step-by-Step Analysis
Scan the whole matrix once, recording every row index and column index that contains a 0, into two sets.
Scan the matrix a second time; for any cell whose row or column is in either set, set that cell to 0.
Return — the original zero positions are still correctly zero, and nothing cascaded.
Complexity
Time: O(m · n) — Space: O(m + n)
Code
def setZeroes(matrix: list[list[int]]) -> None:
rows, cols = set(), set()
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if matrix[r][c] == 0:
rows.add(r)
cols.add(c)
for r in range(len(matrix)):
for c in range(len(matrix[0])):
if r in rows or c in cols:
matrix[r][c] = 0
Code Explanation
How the solution above works, piece by piece.
First pass: collect the indices of every row and column that contains a 0.
Second pass: set a cell to 0 if its row or its column was recorded.
Separating the passes prevents freshly written zeros from being mistaken for original ones.
O(m × n) time, O(m + n) extra space (a constant-space version stores the flags in the first row and column).
Visual Walkthrough
Running it on matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]:
Pass 1 only records which rows and columns contain a zero. Pass 2 zeroes those rows and columns. Recording first matters: zeroing while scanning would create new zeros that wrongly spread further.