Set Matrix Zeroes
Problem
If a cell is 0, set its entire row and column to 0. Do it in place; the follow-up asks for O(1) extra space.
Example 1
Input: [[1,1,1], [1,0,1], [1,1,1]] Output: [[1,0,1], [0,0,0], [1,0,1]]
Test cases
Case 1
Input: [[1,1,1],[1,0,1],[1,1,1]] Expected: [[1,0,1],[0,0,0],[1,0,1]]
Case 2
Input: [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Expected: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Case 3
Input: [[1,2],[3,4]] Expected: [[1,2],[3,4]]
View solutionHide solution2 approaches
1. Row and column sets
Time O(R·C)Space O(R + C)
Record which rows and columns contain a zero, then zero them.
function setZeroes(m) { const rows = new Set(), cols = new Set(); m.forEach((row, r) => row.forEach((v, c) => { if (v === 0) { rows.add(r); cols.add(c); } })); m.forEach((row, r) => row.forEach((_, c) => { if (rows.has(r) || cols.has(c)) row[c] = 0; }));}2. First row and column as markers
Time O(R·C)Space O(1)
Use row 0 and column 0 as the flags. Remember separately whether row 0 / column 0 themselves had a zero, and zero them last.
function setZeroes(m) { const R = m.length, C = m[0].length; const row0 = m[0].includes(0), col0 = m.some((row) => row[0] === 0); for (let r = 1; r < R; r++) for (let c = 1; c < C; c++) if (m[r][c] === 0) { m[r][0] = 0; m[0][c] = 0; } for (let r = 1; r < R; r++) for (let c = 1; c < C; c++) if (m[r][0] === 0 || m[0][c] === 0) m[r][c] = 0; if (row0) m[0].fill(0); if (col0) for (let r = 0; r < R; r++) m[r][0] = 0;}