Given an m x n integer matrix, if any cell holds 0, set its entire row and column to 0.
Do this in place: mutate the input matrix directly and return that same matrix (do not allocate a new one).
Example
The zero at (1,1) clears row 1 and column 1.
Constraints
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Intuition
We can't zero a cell's row and column the instant we see a 0 — those freshly written zeros would look like original zeros to the rest of the scan and cascade outward, eventually wiping the whole matrix. The fix is to decide first, write second: one pass records which rows and which columns contain a zero into two sets, and a second pass zeroes a cell only if its row or column was marked. No write can corrupt a decision, because every decision is already made.
function setZeroes(matrix) {
const zeroRows = new Set();
const zeroCols = new Set();
// Pass 1: only *record* which rows and columns had a zero — write nothing yet.
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 0) {
zeroRows.add(i);
zeroCols.add(j);
}
}
}
// Pass 2: zero a cell iff its row or column was marked — decisions are frozen.
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (zeroRows.has(i) || zeroCols.has(j)) matrix[i][j] = 0;
}
}
return matrix;
}This runs in O(m·n) time, which is optimal — we have to look at every cell at least once. But the two sets cost O(m + n) extra space. Can we do better on space?
The key observation: the matrix already contains m + n cells we could repurpose as marker storage — its first row and first column. Let matrix[0][j] stand in for zeroCols.has(j) and matrix[i][0] for zeroRows.has(i). Scanning the interior (rows and columns from index 1), whenever a cell is 0 we stamp a 0 into its column's header matrix[0][j] and its row's header matrix[i][0]. That is the hash maps marker idea — membership flags — pushed down to O(1) extra space by storing the flags inside the data itself.
The catch is the first row and first column overlap at matrix[0][0] and double as both data and markers, so we can't let them encode their own fate. We track those two with a pair of booleans (firstRowZero, firstColZero) scanned up front, mark and apply the interior from the headers, then zero the first row and first column last from the two booleans. So the stored solution keeps the two-pass decide-then-write spine of the brute force; it just swaps the two Sets for the matrix's own border plus two flags.
Here's that marker scan on a 3x4 grid — the highlighted border holds the flags; watch interior zeros stamp their row and column headers, then the apply pass clear every flagged cell:
matrix = [[1,2,3,4],[5,0,7,8],[9,1,2,0]] — border row/column store the flags
Neither the first row nor the first column holds an original zero, so the border (highlighted) is free to repurpose as marker storage.
Interior zero at (1,1): write 0 into its column header (0,1) and its row header (1,0). The data zero stays put.
Second interior zero at (2,3) stamps header (0,3) and (2,0). The border now flags rows 1, 2 and columns 1, 3.
Second pass clears every interior cell whose row or column header is 0. Both border flags were false, so the first row and column keep their non-marker values — the matrix is done.
Optimization
First row and column as markers
Use the matrix's own first row and column as flags for which columns/rows must be zeroed, plus two booleans for whether the first row and first column themselves contain a zero. Scan the interior to set flags, apply zeroing from the flags, then handle the first row/column last.
O(m·n) time, O(1) extra space.
function setZeroes(matrix) {
const m = matrix.length;
const n = matrix[0].length;
// The first row and column will double as marker storage, so capture their own
// fate up front — these flags decide whether to zero them at the very end.
let firstRowZero = false;
let firstColZero = false;
for (let j = 0; j < n; j++) if (matrix[0][j] === 0) firstRowZero = true;
for (let i = 0; i < m; i++) if (matrix[i][0] === 0) firstColZero = true;
// Pass 1: scan the interior and stamp each zero's row/column into the headers.
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0; // mark this row in the first column
matrix[0][j] = 0; // mark this column in the first row
}
}
}
// Pass 2: apply the marks — clear any interior cell whose header was flagged.
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
}
}
// Finally resolve the border itself from the saved flags (it can't mark itself).
if (firstRowZero) for (let j = 0; j < n; j++) matrix[0][j] = 0;
if (firstColZero) for (let i = 0; i < m; i++) matrix[i][0] = 0;
return matrix; // same instance, mutated in place
}Complexity analysis
Time complexity: O(m·n). Here's why:
- A first sweep over every cell records which rows and columns must be zeroed —
m × ncells. - A second sweep over every cell applies the marks — another
m × ncells.
Both passes are linear in the cell count and run one after the other, so the total is 2 × O(m·n) = O(m·n), where m and n are the matrix's dimensions. We can't do better — any correct solution must inspect every cell at least once.
Space complexity: O(1). Here's why:
- The brute-force baseline keeps two sets,
zeroRowsandzeroCols, holding up tomandnentries — that's O(m + n) extra space. - The stored solution drops both sets: it reuses the matrix's own first row and first column as the marker storage and adds only two booleans (
firstRowZero,firstColZero) — O(1) extra space.
So the optimization trades the O(m + n) sets for O(1) extra space. Nothing new is allocated — the result is the same matrix mutated in place, so there is no output array to count.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| matrix = 123 456 | [[1,2,3],[4,5,6]] | No zero anywhere — the matrix is returned unchanged. |
| matrix = 234 507 891 | [[2,0,4],[0,0,0],[8,0,1]] | A single interior zero at (1,1) clears row 1 and column 1, leaving the corners intact. |
| matrix = 033 456 | [[0,0,0],[0,5,6]] | Zero in the top-left corner — the tricky case for the marker trick, since (0,0) is both a header and data. firstRowZero and firstColZero handle it: row 0 and column 0 both clear. |
| matrix = 12 00 | [[0,0],[0,0]] | An all-zero row marks both columns, so its zeros cascade upward and the whole matrix clears. |
| matrix = 2045 | [[0,0,0,0]] | Single-row 1xN matrix — the only row contains a zero, so the entire row clears. |
| matrix = 2 0 5 | [[0],[0],[0]] | Single-column Nx1 matrix — the zero at (1,0) clears the lone column top to bottom. |
Try it yourself
Write your solution against the real judge before checking the reference.