Set Matrix Zeroes

Medium#73marks on the edges

You get a matrix of numbers. Wherever there is a 0, make its whole row and its whole column 0. Change the matrix in place, and the rows and columns to clear are the ones that had a zero at the start, not ones that got zeros along the way. Our example: [5, 2, 7, 1], [3, 0, 4, 6], [0, 8, 9, 2], [7, 1, 3, 5] → [0, 0, 7, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 3, 5].

73 Set Matrix ZeroesWalkthrough · 1×

Example: [5, 2, 7, 1], [3, 0, 4, 6], [0, 8, 9, 2], [7, 1, 3, 5]. Row 0 gets the mark of column 1 but had no zero of its own, so its 7 and 1 must stay.

012301235271304608927135
not changedthe cell checked nowa mark: 0 in row 0 or column 0set to 0kept its number

Row 0 is [5, 2, 7, 1]: no zero, rowZero = false. Row 0 and column 0 are about to hold the marks, so first remember whether they need clearing themselves

01/34
restart · back · play · step
Speed
1function setZeroes(m):
2 rowZero = row 0 has a 0
3 colZero = column 0 has a 0
4 for each (r, c) with r >= 1 and c >= 1:
5 if m[r][c] == 0:
6 m[r][0] = 0; m[0][c] = 0 // the marks
7 for each (r, c) with r >= 1 and c >= 1:
8 if m[r][0] == 0 or m[0][c] == 0:
9 m[r][c] = 0
10 if rowZero:
11 set row 0 to 0
12 if colZero:
13 set column 0 to 0
14 return m
state
rowZero
false
colZero
–
r
–
c
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Clearing at once would spread: a fresh 0 would look like a zero from the start and clear more rows and columns. So the first pass only marks, and the second one clears.
  2. The marks need a place for every row and every column: column 0 has a cell in each row and row 0 a cell in each column, so the matrix keeps its own marks without extra memory.
  3. A mark written into row 0 looks the same as a zero row 0 had itself, and m[0][0] would serve both row 0 and column 0. The two flags, taken before any mark is written, tell them apart, and row 0 and column 0 are cleared last, after their marks are read.

Complexity

Time O(rows × columns): two passes over the cells, plus row 0 and column 0 twice. Memory O(1): the marks live in the matrix itself, beside two flags.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.