VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.13 of 16 in this moduleFree

Set Matrix Zeroes

If a cell is 0, zero its whole row and column, in place: why zeroing while you scan destroys the answer, then a copy, then row and column flags in O(m + n), then the first row and column as markers in O(1). Then masks, sparse data and NumPy.

about 10 min 6 Python examples 2 quick checks

Problem. Given an m × n matrix, if a cell is 0, set its entire row and column to 0. Do it in place.

text
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.

a 3 by 3 matrix of ones with a zero in the middle; zeroing as you scan cascades into column 2 and row 2, leaving only the top-left 1, while the correct answer zeroes only the middle row and column.
Diagram— a 3 by 3 matrix of ones with a zero in the middle; zeroing as you scan cascades into column 2 and row 2, leaving only the top-left 1, while the correct answer zeroes only the middle row and column.
python
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.

python
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.

python
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?

left, a matrix with separate row flags F, T, T and column flags F, T, F, T; right, the same marks stored as zeros in the matrix's own first row and first column, plus two flags for row 0 and column 0.
Diagram— left, a matrix with separate row flags F, T, T and column flags F, T, F, T; right, the same marks stored as zeros in the matrix's own first row and first column, plus two flags for row 0 and column 0.
python
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?

  1. For speed
  2. 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
  3. Because they are on the edge
  4. It doesn't matter
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.

python
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.

python
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?

  1. The zeros you write are indistinguishable from original zeros, so later cells trigger extra rows and columns; decisions must come from the original data
  2. It's too slow
  3. Python lists can't be modified while iterating
  4. It only fails for square matrices
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

  1. Why does zeroing while scanning fail?
  2. What does the output actually depend on, and how much memory does that need?
  3. Where do the flags live in the O(1) version?
  4. Why are two extra booleans needed?
  5. Why is the order "inner cells, then row 0 and column 0" required?
  6. How do you do it in NumPy?
Answers
  1. Written zeros look like original zeros, so they cascade.
  2. Which rows and which columns contain an original zero: m + n booleans.
  3. Column flags in row 0, row flags in column 0.
  4. 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.
  5. Row 0 and column 0 hold the marks; overwriting them early would corrupt every decision.
  6. rows = (x == 0).any(axis=1), cols = (x == 0).any(axis=0), then x[rows[:, None] | cols[None, :]] = 0.