Problem. Given an m × n matrix, if a cell is 0, set its entire row and column to 0. Do it in place.
1 1 1 1 0 1
1 0 1 → 0 0 0
1 1 1 1 0 1
ML context. This is masking: if a sample has a missing value, drop (zero) the sample; if a feature is broken, drop (zero) the feature everywhere. Attention masks, dropout masks and "invalidate this row and column" updates in similarity matrices are the same shape of problem. The lesson: separate deciding from writing, and find where to store the decisions.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Only original zeros count? | Yes | Zeros you write must not trigger more zeroing |
| In place? | Yes, ideally O(1) extra | Pushes us to store marks inside the matrix |
| Size? | Up to 200 × 200 | O(m·n·(m + n)) ≈ 3 × 10⁶: borderline |
| Values? | Any integers | Rules out a special "marker" value like −1 |
2. Step 2: The tempting wrong answer, then a brute force
The trap: scan the matrix and, at each 0, immediately zero its row and column. The zeros you just wrote look
exactly like original zeros, so later cells trigger more zeroing, and the damage spreads. Trace it: the middle 0
zeroes row 1 and column 1; the scan then reaches m[1][2] (now 0) and zeroes column 2, then m[2][1] (now 0) and
zeroes row 2. Only the top-left cell survives, because it was scanned before the damage reached it.
def set_zeroes_wrong(m):
rows, cols = len(m), len(m[0])
for i in range(rows):
for j in range(cols):
if m[i][j] == 0:
for c in range(cols):
m[i][c] = 0
for r in range(rows):
m[r][j] = 0
m = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
set_zeroes_wrong(m)
print("zeroing while scanning gives:", m)
assert m == [[1, 0, 0], [0, 0, 0], [0, 0, 0]] # wrong: should be [[1,0,1],[0,0,0],[1,0,1]]
Brute force that works: read from an untouched copy, write into the original.
def set_zeroes_copy(m):
rows, cols = len(m), len(m[0])
original = [row[:] for row in m] # O(m · n) extra
for i in range(rows):
for j in range(cols):
if original[i][j] == 0:
for c in range(cols):
m[i][c] = 0
for r in range(rows):
m[r][j] = 0
m = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
set_zeroes_copy(m)
assert m == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
print("copy version works: O(m·n·(m + n)) time, O(m·n) extra space")
Two costs: O(m · n) extra memory for the copy, and O(m · n · (m + n)) time when there are many zeros (each one rewrites a row and a column, often the same ones again).
3. Step 3: Optimise
Optimisation 1: remember rows and columns, not cells (O(m + n) extra)
First principles. The output only depends on which rows contain a zero and which columns contain a zero. That's m + n booleans, not m · n cells. Pass 1 records them; pass 2 writes. Each cell is visited twice: O(m · n) time.
import random
def set_zeroes_flags(m):
rows, cols = len(m), len(m[0])
zero_rows, zero_cols = [False] * rows, [False] * cols # O(m + n)
for i in range(rows):
for j in range(cols):
if m[i][j] == 0:
zero_rows[i] = zero_cols[j] = True
for i in range(rows):
for j in range(cols):
if zero_rows[i] or zero_cols[j]:
m[i][j] = 0
def reference(m):
zr = {i for i, row in enumerate(m) for v in row if v == 0}
zc = {j for row in m for j, v in enumerate(row) if v == 0}
return [[0 if i in zr or j in zc else v for j, v in enumerate(row)] for i, row in enumerate(m)]
rng = random.Random(27)
for _ in range(500):
case = [[rng.choice([0, 1, 2, 3, 4]) for _ in range(rng.randint(1, 5))] for _ in range(1)]
case += [[rng.choice([0, 1, 2, 3, 4]) for _ in range(len(case[0]))] for _ in range(rng.randint(0, 4))]
got = [row[:] for row in case]
set_zeroes_flags(got)
assert got == reference(case)
print("row/column flags: O(m · n) time, O(m + n) extra")
Optimisation 2: store the flags inside the matrix (O(1) extra)
Where can m + n flags live for free? In the matrix itself: the first row can hold the column flags and the
first column can hold the row flags. If m[i][j] == 0, set m[i][0] = 0 and m[0][j] = 0.
One conflict: cell m[0][0] would be both "row 0's flag" and "column 0's flag". And the first row and column have
their own original values to answer for. So keep two extra booleans: did row 0 originally contain a zero, and did
column 0?
import random
def set_zeroes(m):
rows, cols = len(m), len(m[0])
row0_zero = any(m[0][j] == 0 for j in range(cols))
col0_zero = any(m[i][0] == 0 for i in range(rows))
for i in range(1, rows): # 1. mark in row 0 / column 0
for j in range(1, cols):
if m[i][j] == 0:
m[i][0] = 0
m[0][j] = 0
for i in range(1, rows): # 2. fill the inner cells from the marks
for j in range(1, cols):
if m[i][0] == 0 or m[0][j] == 0:
m[i][j] = 0
if row0_zero: # 3. row 0 and column 0 last
for j in range(cols):
m[0][j] = 0
if col0_zero:
for i in range(rows):
m[i][0] = 0
def reference(m):
zr = {i for i, row in enumerate(m) for v in row if v == 0}
zc = {j for row in m for j, v in enumerate(row) if v == 0}
return [[0 if i in zr or j in zc else v for j, v in enumerate(row)] for i, row in enumerate(m)]
m = [[1, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 0]]
set_zeroes(m)
assert m == [[1, 0, 3, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
rng = random.Random(28)
for _ in range(1000):
cols = rng.randint(1, 5)
case = [[rng.choice([0, 1, 2, 3, 4, 5]) for _ in range(cols)] for _ in range(rng.randint(1, 5))]
got = [row[:] for row in case]
set_zeroes(got)
assert got == reference(case)
print("markers in row 0 and column 0: O(m · n) time, O(1) extra, correct on 1,000 cases")
- Time: O(m · n). Extra space: O(1): two booleans.
- Order matters: if you zeroed row 0 first (because it had a zero), you'd destroy the column marks before using them. Inner cells first, the marker row and column last.
Quick check
In the O(1) version, why must row 0 and column 0 be zeroed last?
Show the answer
B. They hold the marks for every other row and column; zeroing them first would make every column (or row) look marked and wipe the matrix — The markers must be read before they are overwritten. That's the same 'decide, then write' rule as the main problem.
4. When the constraints change
| If the constraint becomes… | Best approach | Time | Extra space |
|---|---|---|---|
| Simplest correct | Copy, then write | O(m·n·(m + n)) worst | O(m·n) |
| Clean and fast | Row and column flags | O(m·n) | O(m + n) |
| O(1) extra | Marks in row 0 / column 0 + two flags | O(m·n) | O(1) |
| NumPy array | Boolean masks with any(axis=…) |
O(m·n), vectorised | O(m + n) |
| Huge sparse matrix (few non-zeros stored) | Collect zero rows/cols from the explicit zeros, rebuild | O(nnz) | O(m + n) |
| A sentinel value is safe (e.g. NaN floats) | Mark with the sentinel, then replace | O(m·n·(m + n)) | O(1) |
Change A: NumPy
In NumPy the flags approach is two reductions and a broadcasted mask. Same O(m + n) idea, but the loops run in C.
import numpy as np
x = np.array([[1, 2, 3, 4], [5, 0, 7, 8], [9, 10, 11, 0]])
zero_rows = (x == 0).any(axis=1) # shape (3,)
zero_cols = (x == 0).any(axis=0) # shape (4,)
x[zero_rows[:, None] | zero_cols[None, :]] = 0
assert x.tolist() == [[1, 0, 3, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
print("NumPy: two any() reductions and a broadcasted mask")
Change B: an ML version, dropping samples and features with missing values
Same structure, opposite direction: remove rows and columns rather than zeroing them. Decide which to drop from the original data first, then build the result. Doing it greedily (drop a row, recheck) would give a different answer, the same trap as zeroing while scanning.
import numpy as np
data = np.array([[1.0, 2.0, np.nan], [4.0, 5.0, 6.0], [7.0, np.nan, 9.0], [1.0, 1.0, 1.0]])
bad_features = np.isnan(data).mean(axis=0) > 0.4 # drop features missing in > 40% of rows
kept = data[:, ~bad_features]
kept = kept[~np.isnan(kept).any(axis=1)] # then drop rows still missing values
assert kept.shape == (2, 3)
print("decide from the original data, then drop: shape", kept.shape)
Quick check
Why does zeroing a row and column the moment you see a 0 give the wrong answer?
Show the answer
A. The zeros you write are indistinguishable from original zeros, so later cells trigger extra rows and columns; decisions must come from the original data — Mixing reading and writing corrupts the input you're still reading. Record decisions first, then apply them.
5. Saying it out loud
"Zeroing as I scan would let new zeros trigger more zeroing, so I must decide first and write second. A copy works but costs O(m·n) memory. The answer only depends on which rows and columns contain a zero, so m + n flags suffice: O(m·n) time, O(m + n) space. For O(1) I store those flags in the first row and column, keep two booleans for row 0 and column 0, fill the inner cells, and do the first row and column last."
Check yourself
- Why does zeroing while scanning fail?
- What does the output actually depend on, and how much memory does that need?
- Where do the flags live in the O(1) version?
- Why are two extra booleans needed?
- Why is the order "inner cells, then row 0 and column 0" required?
- How do you do it in NumPy?
Answers
- Written zeros look like original zeros, so they cascade.
- Which rows and which columns contain an original zero: m + n booleans.
- Column flags in row 0, row flags in column 0.
m[0][0]can't hold both row 0's and column 0's flag, and row 0 and column 0 need to remember their own original zeros.- Row 0 and column 0 hold the marks; overwriting them early would corrupt every decision.
rows = (x == 0).any(axis=1),cols = (x == 0).any(axis=0), thenx[rows[:, None] | cols[None, :]] = 0.