Set Matrix Zeroes

Medium

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]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}