LeetCode #73 Medium

Set Matrix Zeroes

If a cell is 0, set its entire row and column to 0in place.

arraymatrixhash-table
Open on LeetCode ↗
02

Intuition

💡

Mutating as you scan would corrupt later checks, so first record which rows and columns must be zeroed, then apply the changes in a second pass.

03

Approach

1

Zeroing as you scan corrupts the scan

The tempting move — when you find a 0, immediately zero out its whole row and column — is a trap. Those freshly written zeros are indistinguishable from original zeros, so the rest of the scan mistakes them for triggers and cascades, zeroing far more than it should. The fix is to never let detection and mutation happen at the same time.

2

Separate detection from mutation

Make a first pass that only records which rows and which columns contain at least one original zero, storing their indices in two sets. This pass changes nothing, so there's no cascade — every zero it sees is a real one from the input.

3

Apply the flags in a second pass

Now sweep the grid again and set a cell to 0 if its row index or its column index was flagged. Because the flags were all computed from the original matrix, the result is exactly right regardless of overlap (set membership is idempotent, so a cell at a flagged row and column is just zeroed once). Two passes: O(m·n) time, O(m + n) space for the two sets.

04

Solution & live demo

python
1class Solution:
2 def setZeroes(self, matrix):
3 rows, cols = set(), set()
4 for i, row in enumerate(matrix):
5 for j, v in enumerate(row):
6 if v == 0:
7 rows.add(i)
8 cols.add(j)
9 for i, row in enumerate(matrix):
10 for j in range(len(row)):
11 if i in rows or j in cols:
12 row[j] = 0
05

Edge cases

No zeros present

Both sets stay empty, so the second pass changes nothing.

Entire matrix is zero

Every row and column is flagged; the whole matrix stays zero after the second pass.

A zero shared by a flagged row and column

Set membership is idempotent, so overlapping flags simply zero the cell once.

06

Complexity

Time
O(m·n)
Space
O(m + n)
Two passes; the sets store at most one entry per row and column.