Set Matrix Zeroes
Record first, zero second
Zeroing cells while you're still scanning for zeros is a trap — a zero you just wrote would look like an original zero and cascade into rows/columns that shouldn't be touched. So split it into two passes: first scan and just remember which rows and columns contain a zero, then a second pass actually writes the zeros using that record.
Details
Animated on: matrix = [[1,1,1],[1,0,1],[1,1,1]] — if a cell is 0, zero its entire row and column (shown flattened row-major, index = row*3+col; the single 0 is at idx4, row1 col1).
Problem:Set Matrix ZeroesMedium
Record first, zero second
step 1 / 8
First pass: scan for zeros, remembering which rows/cols they're in — without zeroing yet, to avoid cascading.
- scan=0· arr[0] = 1
1FUNCTION setZeroes(matrix):2 make an empty set of zero-rows and an empty set of zero-cols3 FOR each cell (r,c):4 IF matrix[r][c] is 0: add r to zero-rows and add c to zero-cols5 FOR each cell (r,c):6 IF r is in zero-rows or c is in zero-cols: set matrix[r][c] = 0
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- First pass: scan for zeros, remembering which rows/cols they're in — without zeroing yet, to avoid cascading.
- idx1 = 1 (row0,col1) — not a zero.
- idx3 = 1 (row1,col0) — not a zero.
- idx4 = 0 (row1,col1) — found a zero! Record: row1 and col1 must be zeroed in the second pass.
- Scan the rest of the cells: all 1s. No more zeros found — zeroRows={1}, zeroCols={1}.
- Second pass: zero out all of row1 — idx3, idx4, idx5 become 0.
- Zero out all of col1 — idx1, idx4, idx7 become 0 (idx4 was already 0 from the row pass).
- Final result: [1,0,1,0,0,0,1,0,1] — row1 and col1 are entirely zeroed out.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.