Set Matrix Zeroes: Zero Out Rows and Columns in Place

Problem

You are given an m×n matrix of integers. For every cell that is 0 in the original matrix, set every cell in its row and its column to 0. Modify the matrix in place. Only zeros present at the start count; zeros you write do not trigger further zeroing. This is widely known as LeetCode 73, Set Matrix Zeroes.

Examples

[[4, 0, 6],         [[0, 0, 0],
 [7, 8, 9],    ->    [7, 0, 9],
 [1, 2, 3]]          [1, 0, 3]]

[[0, 5],            [[0, 0],
 [6, 7]]       ->    [0, 7]]

Approach 1: brute force

Record the rows and columns that contain a zero in two sets, then make a second pass and zero any cell whose row or column is marked.

def set_zeroes_sets(matrix):
    rows, cols = set(), set()
    for r, row in enumerate(matrix):
        for c, v in enumerate(row):
            if v == 0:
                rows.add(r)
                cols.add(c)
    for r, row in enumerate(matrix):
        for c in range(len(row)):
            if r in rows or c in cols:
                row[c] = 0

Complexity: O(m·n) time, O(m + n) extra space. (Copying the whole matrix first would also work, at O(m·n) space.)

Approach 2: optimal

Key insight: the first row and first column can serve as the two marker arrays. Their own original contents are captured in two booleans before they are overwritten.

Steps:

1. Note whether row 0 has a zero (first_row_zero) and whether column 0 has a zero (first_col_zero).
2. For every inner cell (r, c) with r, c ≥ 1 that is 0, set matrix[r][0] = 0 and matrix[0][c] = 0.
3. For every inner cell, zero it if its row marker or column marker is 0.
4. Finally zero row 0 if first_row_zero, and column 0 if first_col_zero.

Walkthrough on [[4, 0, 6], [7, 8, 9], [1, 2, 3]]: row 0 has a zero, column 0 has none. No inner cell is zero, so no new markers. In step 3, cells in column 1 see marker matrix[0][1] = 0 and become 0. Step 4 zeroes row 0. Result [[0, 0, 0], [7, 0, 9], [1, 0, 3]].

def set_zeroes(matrix):
    if not matrix or not matrix[0]:
        return
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(n))
    first_col_zero = any(matrix[r][0] == 0 for r in range(m))
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row_zero:
        for c in range(n):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(m):
            matrix[r][0] = 0

Complexity: O(m·n) time, O(1) extra space.

Tests

import copy, random

def apply(f, m):
    m = copy.deepcopy(m)
    f(m)
    return m

def reference(m):
    rows = {r for r, row in enumerate(m) for v in row if v == 0}
    cols = {c for row in m for c, v in enumerate(row) if v == 0}
    return [[0 if r in rows or c in cols else v for c, v in enumerate(row)] for r, row in enumerate(m)]

for f in (set_zeroes, set_zeroes_sets):
    assert apply(f, [[4, 0, 6], [7, 8, 9], [1, 2, 3]]) == [[0, 0, 0], [7, 0, 9], [1, 0, 3]]
    assert apply(f, [[0, 5], [6, 7]]) == [[0, 0], [0, 7]]            # zero in corner
    assert apply(f, [[1, 2], [3, 4]]) == [[1, 2], [3, 4]]            # no zeros
    assert apply(f, [[0]]) == [[0]] and apply(f, [[9]]) == [[9]]     # 1×1
    assert apply(f, []) == [] and apply(f, [[]]) == [[]]             # empty
    assert apply(f, [[1, 0, 3, 0]]) == [[0, 0, 0, 0]]                # single row
    assert apply(f, [[1], [0], [2]]) == [[0], [0], [0]]              # single column
    assert apply(f, [[-1, 2], [3, 0]]) == [[-1, 0], [0, 0]]          # inner zero, negatives
    assert apply(f, [[10**9, 1], [0, 2]]) == [[0, 1], [0, 0]]        # large values

random.seed(16)
for _ in range(300):
    m = [[random.choice([0, 1, 2, -3]) for _ in range(random.randint(1, 5))]]
    m += [[random.choice([0, 1, 2, -3]) for _ in range(len(m[0]))] for _ in range(random.randint(0, 4))]
    assert apply(set_zeroes, m) == apply(set_zeroes_sets, m) == reference(m)

Edge cases and pitfalls

• Zeroing cells during the first scan is the classic bug: the new zeros are later mistaken for original ones and wipe out the whole matrix.
• In the O(1) version, matrix[0][0] is shared by row 0 and column 0, which is why two separate booleans are needed for them.
• Process the first row and column last; zeroing them early destroys the markers for the inner cells.

Where this shows up in data engineering

The two-pass “mark, then apply” pattern is how you avoid acting on your own writes: collect the keys to change in one pass, apply them in a second. It is the same reason a DELETE with a subquery on the same table is evaluated against a snapshot rather than row by row as it deletes.