Set Matrix Zeroes
MediumMatrix
You get an m × n matrix of integers. Wherever a cell holds 0, set every cell in its row and every cell in its column to 0.
Change matrix itself; the function returns nothing. The tests read matrix after your function returns. Only the zeros that were there at the start spread: a cell you have just set to 0 does not clear its own row and column.
Examples
Input: matrix = [[4, 0, 2], [7, 5, 3], [1, 8, 6]] Output: [[0, 0, 0], [7, 0, 3], [1, 0, 6]]
The 0 sits in row 0 and column 1, so both are cleared.
Input: matrix = [[1, 2, 3, 4], [0, 5, 6, 7], [8, 9, 1, 0]] Output: [[0, 2, 3, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Two zeros clear rows 1 and 2 and columns 0 and 3. Only 2 and 3 in the top row survive.
Constraints
1 ≤ m, n ≤ 200-2³¹ ≤ matrix[i][j] ≤ 2³¹ - 1
Stuck?
Hint 1
If you clear rows and columns while you are still scanning, the new zeros look like original ones and spread too. Find every zero first, then clear.
Hint 2
Remember which rows and which columns hold a zero (two Sets work), then make a second pass. For O(1) space, keep those marks in the first row and first column, with one extra flag for the first column itself.
The idea
Only the zeros that were there at the start may spread. If you clear rows and columns while still scanning, the zeros you write look the same as the original ones and spread too. So find every zero first, then clear in a second pass.
Time O(m · n)Extra space O(m + n) for the marked rows and columns
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 3
Keep the rows and the columns that hold a zero, not the cells. The Sets take O(m + n) space; keeping the same marks in the matrix's own first row and first column brings that down to O(1).
function setZeroes(matrix) { const zeroRows = new Set(); const zeroCols = new Set(); matrix.forEach((row, r) => row.forEach((value, c) => { if (value === 0) { zeroRows.add(r); zeroCols.add(c); } }) ); matrix.forEach((row, r) => row.forEach((_, c) => { if (zeroRows.has(r) || zeroCols.has(c)) row[c] = 0; }) );}The trap
This version clears a row and a column the moment it finds a zero, while the scan is still running. The cells it sets to 0 are reached later in the same scan and clear their own rows and columns. One zero near the top left can wipe out the whole matrix, while a lone zero in the bottom right corner comes out right, which is why a quick test can miss it.
function setZeroes(matrix) { for (let r = 0; r < matrix.length; r++) { for (let c = 0; c < matrix[0].length; c++) { if (matrix[r][c] === 0) { // clears while scanning, so the new zeros spread as well for (let j = 0; j < matrix[0].length; j++) matrix[r][j] = 0; for (let i = 0; i < matrix.length; i++) matrix[i][c] = 0; } } }}