When a cell is zero, its entire row and column must be zeroed — and the trick is doing it without extra space by repurposing the first row and first column as in-place boolean flags.
Given an m × n integer matrix, if any cell is 0, set its entire row and column to 0 — in place. For example:
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
The zero at [1][1] wipes row 1 and column 1.
matrix[0][c] = 0 means "zero column c", matrix[r][0] = 0means "zero row r". You just need to save whether the first row and first column themselves originally had a zero before you overwrite them.firstRowZero / firstColZero booleans. You need this before those cells become marker storage.r≥1, c≥1). When matrix[r][c] === 0, set matrix[0][c] = 0 and matrix[r][0] = 0. These markers are why you need no extra array.matrix[0][c] === 0 or matrix[r][0] === 0, set matrix[r][c] = 0.firstRowZero, zero all of row 0. If firstColZero, zero all of col 0. This step must come last; zeroing row 0 first would corrupt the flags.Both approaches run in O(m·n) time (two full passes). The O(m+n) approach is easier to reason about; the O(1) approach is what interviewers ask for once the naive solution is on the board.
function setZeroes(matrix: number[][]): void {
const rows = matrix.length;
const cols = matrix[0].length;
// Remember whether row 0 / col 0 themselves need zeroing
// BEFORE we overwrite them as marker storage.
let firstRowZero = false;
let firstColZero = false;
for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRowZero = true;
for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstColZero = true;
// Pass 1: scan interior; mark row 0 / col 0 as flags.
for (let r = 1; r < rows; r++) {
for (let c = 1; c < cols; c++) {
if (matrix[r][c] === 0) {
matrix[0][c] = 0; // flag: column c needs zeroing
matrix[r][0] = 0; // flag: row r needs zeroing
}
}
}
// Pass 2: zero interior cells driven by the flags.
for (let r = 1; r < rows; r++) {
for (let c = 1; c < cols; c++) {
if (matrix[0][c] === 0 || matrix[r][0] === 0) {
matrix[r][c] = 0;
}
}
}
// Handle first row / col last (they were used as scratch).
if (firstRowZero) {
for (let c = 0; c < cols; c++) matrix[0][c] = 0;
}
if (firstColZero) {
for (let r = 0; r < rows; r++) matrix[r][0] = 0;
}
}r≥1, c≥1). A zero at [r][c] sets matrix[0][c] (flag for column c) and matrix[r][0] (flag for row r). No cell is zeroed yet — pure discovery.matrix[0][c] or the row flag matrix[r][0] is zero, this cell must be zeroed. Because we wrote the flags in a prior pass, no confusion from freshly-written zeros.firstRowZero and firstColZero — captured before pass 1 — now tell us whether to wipe them. Doing this last ensures the flags remain valid throughout pass 2.Set<number> of zero rows and another of zero columns, then do a second pass to zero them. Easy to code, clear to explain — good starting point before optimizing to O(1).[r][c]propagates zeros into cells you haven't visited yet, causing those to incorrectly trigger more row/column wipes. The two-pass design eliminates this contamination.matrix[0][0] to represent row 0. One less boolean, same logic.| "set entire row and column to zero" | two-pass in-place markers |
| matrix mutation, O(1) space requested | repurpose first row/col as flags |
| corrupt-if-you-write-while-scanning | separate mark pass from write pass |
| "in place" + boolean state per row/col | row 0 = col flags, col 0 = row flags |
// 1. Check if row 0 / col 0 originally contain a zero.
let firstRowZero = false, firstColZero = false;
// ... scan row 0 and col 0 ...
// 2. Scan interior; mark row 0 / col 0.
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++)
if (matrix[r][c] === 0) { matrix[0][c] = 0; matrix[r][0] = 0; }
// 3. Zero interior using the flags.
for (let r = 1; r < rows; r++)
for (let c = 1; c < cols; c++)
if (matrix[0][c] === 0 || matrix[r][0] === 0) matrix[r][c] = 0;
// 4. Handle first row / col (must be last).
if (firstRowZero) { /* zero row 0 */ }
if (firstColZero) { /* zero col 0 */ }[[0,1,2,0],[3,4,5,2],[1,3,1,5]], which cells act as markers after pass 1?[[1,1,1],[1,0,1],[1,1,1]]. What is the output?