You're given an m × n matrix of numbers. Wherever a cell holds a 0, that zero "infects" its entire row and its entire column — every cell in that row and that column must become 0 too. Your job is to apply this rule across the whole matrix and return the result. This is the classic Set Matrix Zeroes problem; the catch is that only the zeros present in the original matrix trigger the rule.
// matrix: number[][] — an m×n grid (m rows, n columns)
// returns the same matrix, mutated in place, with rows and columns zeroed.
function matrixZeroing(matrix: number[][]): number[][];A single zero zeroes its row and its column, and nothing else:
matrixZeroing([
[1, 2, 3],
[4, 0, 6],
[7, 8, 9],
]);
// → [
// [1, 0, 3], // column 1 cleared
// [0, 0, 0], // row 1 cleared
// [7, 0, 9], // column 1 cleared
// ]Two zeros each clear their own row and column; the cleared regions overlap:
matrixZeroing([
[0, 2, 3, 4],
[5, 6, 7, 8],
[9, 1, 0, 2],
]);
// → [
// [0, 0, 0, 0], // row 0 cleared (and col 0, col 2)
// [0, 6, 0, 8], // col 0 and col 2 cleared
// [0, 0, 0, 0], // row 2 cleared (and col 0, col 2)
// ]0 because of the rule must NOT go on to zero its own row and column. Only the zeros present in the matrix you were handed count.[], [[]], a single row, a single column, and a 1 × 1 matrix must all be handled without throwing.You'll take a grid of numbers and, for every cell that originally held a 0, blank out that cell's whole row and whole column — then return the same grid, mutated.
Imagine a spreadsheet where any blank cell means "this whole row and this whole column are unreliable, grey them all out." You scan the sheet, find the blanks, and grey out their rows and columns. The one rule that makes this tricky: a cell you greyed out is not itself a blank you found — it doesn't get to grey out its own row and column. Only the blanks that were there when you started count. Translate "blank" to 0 and "grey out" to "set to 0" and that's exactly this problem.
The whole difficulty lives in one word: original. A zero that was in the input triggers the rule. A zero you write while applying the rule does not. So you need to separate two phases that the naive code tangles together — deciding what to clear and clearing it. As long as every clearing decision is made by reading the untouched original (or a record of it), and no clearing happens until all decisions are made, the cascade can't start.
The cleanest record is two sets: the set of row indices that contain a zero, and the set of column indices that contain a zero. Collect both in one pass, then clear in a second pass.
The obvious move is a single loop: when you hit a 0, immediately zero its row and column. Decision and action in one place.
function matrixZeroingNaive(matrix) {
const rows = matrix.length;
const cols = matrix[0]?.length ?? 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (matrix[r][c] === 0) {
for (let k = 0; k < cols; k++) matrix[r][k] = 0; // clear row r
for (let k = 0; k < rows; k++) matrix[k][c] = 0; // clear column c
}
}
}
return matrix;
}Run it on [[1, 0], [1, 1]]. The original has one zero, at [0][1]. The correct result clears row 0 and column 1, leaving [[0, 0], [1, 0]]. But watch what this code does: it finds the 0 at [0][1], clears row 0 and column 1 — which writes a fresh 0 into [1][1]. The outer loop keeps scanning, reaches [1][1], sees a 0, and treats it as a trigger. Now it clears row 1 too, blanking [1][0] that should have stayed 1. The written zeros feed back into the scan and cascade. On larger matrices a single original zero can wipe everything.
The fix isn't a clever guard inside this loop — it's to stop reading and writing the matrix at the same time.
function matrixZeroing(matrix) {
const rows = matrix.length;
// Guard the empty / degenerate shapes: [], [[]], etc. No rows or no
// columns means there is nothing to scan and nothing to clear.
const cols = rows > 0 ? matrix[0].length : 0;
if (rows === 0 || cols === 0) return matrix;
const zeroRows = new Set(); // row indices that held an original zero
const zeroCols = new Set(); // column indices that held an original zero
// Pass 1: scan the untouched matrix, record only. We never write here,
// so a zero we would later create cannot be mistaken for an original.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (matrix[r][c] === 0) {
zeroRows.add(r);
zeroCols.add(c);
}
}
}
// Pass 2: clear. A cell dies if its row OR its column was recorded.
// The membership test reads the Sets, not the matrix, so the zeros we
// write never influence later decisions.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (zeroRows.has(r) || zeroCols.has(c)) {
matrix[r][c] = 0;
}
}
}
return matrix;
}
module.exports = { matrixZeroing };The shift from the naive version is small but total. The decision and the action are now in different loops. Pass 1 answers "which rows and columns are doomed?" by reading the original matrix; nothing changes while it runs. Pass 2 acts on those answers by reading the Sets, never the matrix — so when it writes a 0 into a cell, the cell next door doesn't care, because its fate was decided by zeroRows/zeroCols, which Pass 2 never modifies.
A few line-level choices worth calling out. The empty-shape guard handles [] (no rows) and [[]] (a row with no columns); without it, matrix[0].length on [] would read undefined.length and throw. zeroRows.has(r) || zeroCols.has(c) is the entire rule in one line: a cell is cleared if it shares a row with an original zero or shares a column with one. Returning matrix satisfies the in-place contract — we mutated the caller's array and hand the same reference back, so matrixZeroing(x) === x.
Trace the two-zero example from the prompt: [[0, 2, 3, 4], [5, 6, 7, 8], [9, 1, 0, 2]]. There are two original zeros — at [0][0] and at [2][2].
Pass 1 — scan and record (matrix untouched):
[0][0] === 0 → zeroRows.add(0), zeroCols.add(0)
[2][2] === 0 → zeroRows.add(2), zeroCols.add(2)
every other cell is nonzero → no change
zeroRows = { 0, 2 }
zeroCols = { 0, 2 }
Pass 2 — clear when row OR column is recorded:
row 0: in zeroRows → entire row becomes 0 → [0, 0, 0, 0]
row 1: not in zeroRows; clear only cols 0 and 2
[1][0] col 0 ✓→0 [1][1] col 1 ✗ [1][2] col 2 ✓→0 [1][3] col 3 ✗
→ [0, 6, 0, 8]
row 2: in zeroRows → entire row becomes 0 → [0, 0, 0, 0]
result = [[0, 0, 0, 0], [0, 6, 0, 8], [0, 0, 0, 0]]
Notice [1][1] (value 6) survives: row 1 was never recorded and column 1 was never recorded, so neither set claims it. That single surviving cell is the proof the cascade never happened — the naive approach would have clobbered it the moment it wrote a zero into row 1.
[[1, 0], [1, 1]] the naive code wrongly clears row 1; on a sparse large matrix one zero can spread to the entire grid. Fix: collect every doomed row/column before writing anything.NaN and clear on the second pass — but the moment your record lives inside the matrix you're back to mixing data and markers, and you have to prove the sentinel can never collide with real data. Two Sets keep the record cleanly outside the data.[r][c], it adds r to zeroRows and c to zeroCols — and clearing checks zeroRows.has(r) || zeroCols.has(c). Swap any of those r/c pairings and you clear the transpose of what you meant. Square matrices hide the bug; a non-square input like the 3×4 example above exposes it immediately (you'll index out of bounds or clear the wrong band).[] has no rows; [[]] has a row with zero columns. Reading matrix[0].length on [] throws, and an unguarded inner loop on [[]] does nothing useful. Guard rows === 0 || cols === 0 up front and return the matrix unchanged.matrixZeroing(x) === x fails and callers holding the original reference see stale data. Mutate matrix directly and return matrix.O(1) extra space using the first row and column as markers. Instead of two Sets, use the matrix's own first row to flag "this column has a zero" and its first column to flag "this row has a zero." Cell [0][0] is shared by both, so track whether the first row (or first column) itself needs clearing with one extra boolean. The order matters: scan and set markers, clear the inner grid [1..][1..] using the markers, then clear the first row/column last — because they double as both markers and data. Same answer, O(1) extra space instead of O(m + n).
Sparse representation. If the matrix is huge and mostly nonzero, you don't need the grid at all to decide what to clear — a list of the (r, c) coordinates of original zeros is enough, and you can store the result as "all cells except those whose row and column are both clear." For genuinely sparse data, a coordinate list (or two index sets) is far smaller than m × n cells.
Immutable copy variant. Some callers want the original left intact. Build the answer into a fresh result array: run Pass 1 against the input to fill zeroRows/zeroCols, then in Pass 2 write into result[r][c] instead of matrix[r][c], copying the original value through when neither set claims the cell. Same two-pass logic, O(m · n) extra space, and the input is untouched.
Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given an m × n matrix of numbers. Wherever a cell holds a 0, that zero "infects" its entire row and its entire column — every cell in that row and that column must become 0 too. Your job is to apply this rule across the whole matrix and return the result. This is the classic Set Matrix Zeroes problem; the catch is that only the zeros present in the original matrix trigger the rule.
// matrix: number[][] — an m×n grid (m rows, n columns)
// returns the same matrix, mutated in place, with rows and columns zeroed.
function matrixZeroing(matrix: number[][]): number[][];A single zero zeroes its row and its column, and nothing else:
matrixZeroing([
[1, 2, 3],
[4, 0, 6],
[7, 8, 9],
]);
// → [
// [1, 0, 3], // column 1 cleared
// [0, 0, 0], // row 1 cleared
// [7, 0, 9], // column 1 cleared
// ]Two zeros each clear their own row and column; the cleared regions overlap:
matrixZeroing([
[0, 2, 3, 4],
[5, 6, 7, 8],
[9, 1, 0, 2],
]);
// → [
// [0, 0, 0, 0], // row 0 cleared (and col 0, col 2)
// [0, 6, 0, 8], // col 0 and col 2 cleared
// [0, 0, 0, 0], // row 2 cleared (and col 0, col 2)
// ]0 because of the rule must NOT go on to zero its own row and column. Only the zeros present in the matrix you were handed count.[], [[]], a single row, a single column, and a 1 × 1 matrix must all be handled without throwing.You'll take a grid of numbers and, for every cell that originally held a 0, blank out that cell's whole row and whole column — then return the same grid, mutated.
Imagine a spreadsheet where any blank cell means "this whole row and this whole column are unreliable, grey them all out." You scan the sheet, find the blanks, and grey out their rows and columns. The one rule that makes this tricky: a cell you greyed out is not itself a blank you found — it doesn't get to grey out its own row and column. Only the blanks that were there when you started count. Translate "blank" to 0 and "grey out" to "set to 0" and that's exactly this problem.
The whole difficulty lives in one word: original. A zero that was in the input triggers the rule. A zero you write while applying the rule does not. So you need to separate two phases that the naive code tangles together — deciding what to clear and clearing it. As long as every clearing decision is made by reading the untouched original (or a record of it), and no clearing happens until all decisions are made, the cascade can't start.
The cleanest record is two sets: the set of row indices that contain a zero, and the set of column indices that contain a zero. Collect both in one pass, then clear in a second pass.
The obvious move is a single loop: when you hit a 0, immediately zero its row and column. Decision and action in one place.
function matrixZeroingNaive(matrix) {
const rows = matrix.length;
const cols = matrix[0]?.length ?? 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (matrix[r][c] === 0) {
for (let k = 0; k < cols; k++) matrix[r][k] = 0; // clear row r
for (let k = 0; k < rows; k++) matrix[k][c] = 0; // clear column c
}
}
}
return matrix;
}Run it on [[1, 0], [1, 1]]. The original has one zero, at [0][1]. The correct result clears row 0 and column 1, leaving [[0, 0], [1, 0]]. But watch what this code does: it finds the 0 at [0][1], clears row 0 and column 1 — which writes a fresh 0 into [1][1]. The outer loop keeps scanning, reaches [1][1], sees a 0, and treats it as a trigger. Now it clears row 1 too, blanking [1][0] that should have stayed 1. The written zeros feed back into the scan and cascade. On larger matrices a single original zero can wipe everything.
The fix isn't a clever guard inside this loop — it's to stop reading and writing the matrix at the same time.
function matrixZeroing(matrix) {
const rows = matrix.length;
// Guard the empty / degenerate shapes: [], [[]], etc. No rows or no
// columns means there is nothing to scan and nothing to clear.
const cols = rows > 0 ? matrix[0].length : 0;
if (rows === 0 || cols === 0) return matrix;
const zeroRows = new Set(); // row indices that held an original zero
const zeroCols = new Set(); // column indices that held an original zero
// Pass 1: scan the untouched matrix, record only. We never write here,
// so a zero we would later create cannot be mistaken for an original.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (matrix[r][c] === 0) {
zeroRows.add(r);
zeroCols.add(c);
}
}
}
// Pass 2: clear. A cell dies if its row OR its column was recorded.
// The membership test reads the Sets, not the matrix, so the zeros we
// write never influence later decisions.
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (zeroRows.has(r) || zeroCols.has(c)) {
matrix[r][c] = 0;
}
}
}
return matrix;
}
module.exports = { matrixZeroing };The shift from the naive version is small but total. The decision and the action are now in different loops. Pass 1 answers "which rows and columns are doomed?" by reading the original matrix; nothing changes while it runs. Pass 2 acts on those answers by reading the Sets, never the matrix — so when it writes a 0 into a cell, the cell next door doesn't care, because its fate was decided by zeroRows/zeroCols, which Pass 2 never modifies.
A few line-level choices worth calling out. The empty-shape guard handles [] (no rows) and [[]] (a row with no columns); without it, matrix[0].length on [] would read undefined.length and throw. zeroRows.has(r) || zeroCols.has(c) is the entire rule in one line: a cell is cleared if it shares a row with an original zero or shares a column with one. Returning matrix satisfies the in-place contract — we mutated the caller's array and hand the same reference back, so matrixZeroing(x) === x.
Trace the two-zero example from the prompt: [[0, 2, 3, 4], [5, 6, 7, 8], [9, 1, 0, 2]]. There are two original zeros — at [0][0] and at [2][2].
Pass 1 — scan and record (matrix untouched):
[0][0] === 0 → zeroRows.add(0), zeroCols.add(0)
[2][2] === 0 → zeroRows.add(2), zeroCols.add(2)
every other cell is nonzero → no change
zeroRows = { 0, 2 }
zeroCols = { 0, 2 }
Pass 2 — clear when row OR column is recorded:
row 0: in zeroRows → entire row becomes 0 → [0, 0, 0, 0]
row 1: not in zeroRows; clear only cols 0 and 2
[1][0] col 0 ✓→0 [1][1] col 1 ✗ [1][2] col 2 ✓→0 [1][3] col 3 ✗
→ [0, 6, 0, 8]
row 2: in zeroRows → entire row becomes 0 → [0, 0, 0, 0]
result = [[0, 0, 0, 0], [0, 6, 0, 8], [0, 0, 0, 0]]
Notice [1][1] (value 6) survives: row 1 was never recorded and column 1 was never recorded, so neither set claims it. That single surviving cell is the proof the cascade never happened — the naive approach would have clobbered it the moment it wrote a zero into row 1.
[[1, 0], [1, 1]] the naive code wrongly clears row 1; on a sparse large matrix one zero can spread to the entire grid. Fix: collect every doomed row/column before writing anything.NaN and clear on the second pass — but the moment your record lives inside the matrix you're back to mixing data and markers, and you have to prove the sentinel can never collide with real data. Two Sets keep the record cleanly outside the data.[r][c], it adds r to zeroRows and c to zeroCols — and clearing checks zeroRows.has(r) || zeroCols.has(c). Swap any of those r/c pairings and you clear the transpose of what you meant. Square matrices hide the bug; a non-square input like the 3×4 example above exposes it immediately (you'll index out of bounds or clear the wrong band).[] has no rows; [[]] has a row with zero columns. Reading matrix[0].length on [] throws, and an unguarded inner loop on [[]] does nothing useful. Guard rows === 0 || cols === 0 up front and return the matrix unchanged.matrixZeroing(x) === x fails and callers holding the original reference see stale data. Mutate matrix directly and return matrix.O(1) extra space using the first row and column as markers. Instead of two Sets, use the matrix's own first row to flag "this column has a zero" and its first column to flag "this row has a zero." Cell [0][0] is shared by both, so track whether the first row (or first column) itself needs clearing with one extra boolean. The order matters: scan and set markers, clear the inner grid [1..][1..] using the markers, then clear the first row/column last — because they double as both markers and data. Same answer, O(1) extra space instead of O(m + n).
Sparse representation. If the matrix is huge and mostly nonzero, you don't need the grid at all to decide what to clear — a list of the (r, c) coordinates of original zeros is enough, and you can store the result as "all cells except those whose row and column are both clear." For genuinely sparse data, a coordinate list (or two index sets) is far smaller than m × n cells.
Immutable copy variant. Some callers want the original left intact. Build the answer into a fresh result array: run Pass 1 against the input to fill zeroRows/zeroCols, then in Pass 2 write into result[r][c] instead of matrix[r][c], copying the original value through when neither set claims the cell. Same two-pass logic, O(m · n) extra space, and the input is untouched.
Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.