Set Matrix Zeroes
WHAT IT SAYS
If any cell of an m x n matrix is 0, set that cell's entire row and entire column to 0 — in place.
WHAT IT'S REALLY ASKING
"The final value of any cell depends on exactly two facts: is my row doomed, is my column doomed? That's m + n bits of truth deciding m*n cells. So the real question isn't how to compute the answer — it's where to park m + n bits inside a matrix you're already allowed to destroy."
Zero as you go
O(m*n) work per zero, and the output is wrong anywayWalk the matrix; every time you hit a 0, immediately blank its row and column. Simple, and completely wrong — the zeros you write are indistinguishable from the zeros that were there originally, so they trigger more blanking and the whole matrix floods.
WHERE THE WORK IS WASTED — The bug names the real constraint: your output alphabet collides with your input alphabet. A 0 in the matrix is now ambiguous — 'this was always 0' and 'this got zeroed' look identical — so any fix must either copy the original data or find a place to record decisions that the flooding cannot reach.
Remember rows and columns in two arrays
O(m*n) time, O(m + n) spaceFirst pass: record which row indices contain a zero and which column indices do, in a boolean array of size m and one of size n. Second pass: zero every cell whose row or column is flagged. Correct, and the ambiguity is gone because the flags live outside the matrix.
The cells you're about to destroy can carry the message.
You need m + n bits of scratch space and the interviewer says O(1). That sounds impossible until you ask which cells of the matrix still hold information worth protecting. Suppose row i is doomed. Then every cell in it will end as 0 — including matrix[i][0]. Its final value is already decided, so whatever is sitting there now is data nobody will ever read again. That cell is free. Same for a doomed column j and its cell matrix[0][j]. And if row i is NOT doomed, matrix[i][0] is exactly the flag you'd want to be false — so you can use the cell itself as row i's flag, and the encoding is consistent either way: matrix[i][0] == 0 means 'row i dies', and that is true whether it was already 0 or you set it. So the first column is a natural home for the m row-flags, and the first row for the n column-flags. The matrix has enough slack in its own output to store the summary of that output. One collision remains, and it's the only subtle part: matrix[0][0] would have to be the flag for row 0 AND the flag for column 0. Two masters, one bit. So you pull one of them out into a single standalone boolean — the classic choice is a firstColZero flag — and let matrix[0][0] speak only for row 0. One extra variable, still O(1). The ordering falls out of the same logic. Since the first row and column are now *metadata*, you must not overwrite them while you still need to read them: mark from the inner region, then write back the inner region, and only afterwards blank the borders themselves.
Borders as flags, write back inwards-out
O(m*n) time, O(1) extra space, two passesSave whether column 0 originally contains a zero in one boolean. Then scan every cell from (0,1) to (m-1, n-1) and, whenever you see a 0, stamp matrix[i][0] = 0 and matrix[0][j] = 0. Now walk the interior backwards — from the bottom-right up to (1,1) — zeroing any cell whose row-flag or column-flag is 0; going backwards means you read each border flag before anything could clobber it. Finally handle row 0 using matrix[0][0], and column 0 using your saved boolean.
The Output Is the Scratchpad
YOU'LL SEE IT AGAIN WHEN
- The statement demands in-place / O(1) extra space, but the naive solution's bookkeeping is much smaller than the data itself.
- Writing your answer into the structure corrupts the input you still need to read — so the traversal order or an encoding trick has to separate 'was' from 'became'.
- Some part of the structure has a value that is already fully determined, meaning nothing is lost by overwriting it early.