Set Matrix Zeroes

This problem looks like a two-minute exercise and is asked because the obvious in-place version is wrong in a subtle way. The interviewer wants three answers in turn: a copy, two sets, and the constant-space version that stores its bookkeeping inside the matrix itself.

The problem

You get an m × n matrix of integers. If any cell is 0, set every cell in its row and its column to 0. Do it in place.

Example 1.

input            output1  2  3  4       1  0  3  05  0  7  8       0  0  0  09 10 11  0       0  0  0  0

The 0 at (1, 1) clears row 1 and column 1. The 0 at (2, 3) clears row 2 and column 3.

Example 2. [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] → [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]].

Constraints. 1 ≤ m, n ≤ 200. Values fit in 32-bit integers. The follow-up asks for O(1) extra space.

Clarifying questions

• Only zeros that were in the original matrix count? Yes. A 0 we write must not trigger more clearing. This is the heart of the problem.
• Can the matrix be a single row or column? Yes.
• Is every value possibly 0? Yes, including the corner (0, 0).

Approach 1: the simple way

Keep a copy of the original. Read zeros from the copy, write zeros into the matrix.

1def set_zeroes_copy(matrix: list[list[int]]) -> None:2    """Brute force: find zeros in a copy, clear rows and columns in the original."""3    original = [row[:] for row in matrix]4    rows, cols = len(matrix), len(matrix[0])5    for r in range(rows):6        for c in range(cols):7            if original[r][c] == 0:8                for k in range(cols):9                    matrix[r][k] = 010                for k in range(rows):11                    matrix[k][c] = 0

This is correct, but it costs O(m × n) extra space for the copy and O(m × n × (m + n)) time in the worst case, since each zero clears a whole row and column. Why the copy? Without it, clearing a row writes zeros that later look like original zeros. On [[1, 1, 1], [1, 0, 1], [1, 1, 1]], the immediate version cascades: the correct answer is [[1, 0, 1], [0, 0, 0], [1, 0, 1]], but writing zeros as you go produced [[1, 0, 0], [0, 0, 0], [0, 0, 0]].

A better middle step: record the indices of rows and columns that contain a 0 in two sets, then clear in a second pass. That is O(m × n) time and O(m + n) space.

The key insight

The sets only store one yes/no flag per row and one per column. We need somewhere to put m + n flags without extra memory — and the matrix has a row of n cells and a column of m cells sitting right there: row 0 and column 0.

So use matrix[r][0] = 0 to mean "row r must be cleared" and matrix[0][c] = 0 to mean "column c must be cleared". Writing a 0 there is safe, because that cell is in a row (or column) that is going to be zeroed anyway.

Two details make it correct:

1. Cell (0, 0) is shared. It cannot mean both "clear row 0" and "clear column 0". Let it mean "clear row 0", and keep one extra boolean, first_col_zero, for column 0.
2. Apply the markers last-in, first-out. Row 0 and column 0 hold the markers, so they must be the last cells overwritten. Process from the bottom-right corner back to the top-left, and do column 0 of each row after that row's other cells.

Approach 2: markers in row 0 and column 0

1def set_zeroes(matrix: list[list[int]]) -> None:2    """O(1) space: row 0 and column 0 store which rows and columns to clear."""3    rows, cols = len(matrix), len(matrix[0])4    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))56    for r in range(rows):                     # pass 1: record markers7        for c in range(1, cols):8            if matrix[r][c] == 0:9                matrix[r][0] = 0              # row r must be cleared10                matrix[0][c] = 0              # column c must be cleared1112    for r in range(rows - 1, -1, -1):         # pass 2: apply, bottom-up13        for c in range(cols - 1, 0, -1):14            if matrix[r][0] == 0 or matrix[0][c] == 0:15                matrix[r][c] = 016        if first_col_zero:17            matrix[r][0] = 0

Step by step:

1. Before anything is written, note whether column 0 has an original zero.
2. Pass 1 scans every cell except column 0. For each zero, mark its row in column 0 and its column in row 0.
3. Pass 2 walks rows from the bottom up and columns from right to left, zeroing any cell whose row or column is marked. Column 0 of each row is handled last, by the boolean.

Dry run on Example 1. first_col_zero is False (column 0 holds 1, 5, 9).

The result, 1 0 3 0 / 0 0 0 0 / 0 0 0 0, matches the expected output. Notice (0, 0) is still 1: no original zero sat in row 0 or column 0.

Complexity. O(m × n) time — two passes over the matrix. O(1) extra space — one boolean.

The marker version matched both the copy version and the two-sets version on 400 random matrices of every shape up to 6 × 6.

Edge cases

• A zero in row 0 or column 0 originally. Example 2 has zeros at (0, 0) and (0, 3). first_col_zero is True, so column 0 is cleared, and the marker at (0, 0) clears row 0.
• A single row or column. The same code works: with one column, pass 1 does nothing and the boolean does all the work.
• No zeros. No markers are written; pass 2 changes nothing.
• All zeros. Every marker is set; everything stays 0.

Follow-ups

• "Why not just use a special value like -1 instead of 0 in pass 1?" Because the matrix may contain any integer, including -1. A sentinel only works if a value is guaranteed unused — ask before relying on one.
• "Do the two-sets version in less code." zero_rows = {r for r, row in enumerate(matrix) if 0 in row} and similarly for columns via zip(*matrix). Fine in production; say it is O(m + n) space.
• "The matrix is huge and stored on disk." Two passes are still enough: one streaming pass to collect the row and column flags (m + n bits), one to rewrite.