Set Matrix Zeroes (LeetCode 73)

The problem

You get an m × n matrix of integers. Wherever a cell is 0, set its entire row and entire column to 0. Do it in place, ideally with O(1) extra space.

Input:
1  2  3  4
5  0  7  8
9 10 11  0

Output:
1  0  3  0
0  0  0  0
0  0  0  0

The 0 at (1, 1) wipes row 1 and column 1; the 0 at (2, 3) wipes row 2 and column 3.

How to think about it

Start with brute force. Copy the matrix, scan the copy for zeros, and zero rows and columns in the original. That is O(m·n) extra space. Zeroing as you scan, without a copy, is wrong: the new zeros you write look exactly like original zeros, and they spread until the whole matrix is 0.

Better: remember only which rows and columns to clear. You don’t need the whole copy, just two sets (or boolean arrays): zero_rows and zero_cols. One pass fills them, a second pass zeroes cell (r, c) if r or c is marked. That is O(m + n) space and is a perfectly good answer to give first.

The key insight: the matrix already has an m-cell column and an n-cell row you can borrow. Use row 0 as the column markers and column 0 as the row markers. If matrix[r][c] is 0, set matrix[r][0] = 0 and matrix[0][c] = 0. Those cells are going to become 0 anyway, so writing a marker there loses nothing.

The catch is row 0 and column 0 themselves. Once you write markers into them, you can no longer tell whether they held an original 0. So check them first, saving two booleans, then only process the inner cells, and clear row 0 and column 0 last. The tell for this pattern is “in place, O(1) extra space, on a matrix”: look for space inside the input that you can reuse.

Approach

1. Record first_row: does row 0 contain a 0? Record first_col: does column 0 contain a 0?
2. For every inner cell (r, c) with r ≥ 1 and c ≥ 1: if it is 0, mark matrix[r][0] = 0 and matrix[0][c] = 0.
3. For every inner cell again: if its row marker or column marker is 0, set it to 0.
4. If first_row, zero all of row 0. If first_col, zero all of column 0.

Solution

def set_zeroes(matrix):
    R, C = len(matrix), len(matrix[0])
    first_row = any(matrix[0][c] == 0 for c in range(C))   # save before markers overwrite
    first_col = any(matrix[r][0] == 0 for r in range(R))
    for r in range(1, R):
        for c in range(1, C):
            if matrix[r][c] == 0:
                matrix[r][0] = 0; matrix[0][c] = 0          # write markers
    for r in range(1, R):
        for c in range(1, C):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0                            # apply markers to inner cells
    if first_row:
        for c in range(C): matrix[0][c] = 0                 # marker row/col cleared last
    if first_col:
        for r in range(R): matrix[r][0] = 0
    return matrix
# set_zeroes([[1,1,1],[1,0,1],[1,1,1]]) -> [[1,0,1],[0,0,0],[1,0,1]]

Dry run

On the 3 × 4 example:

Row 0 keeps 1 and 3 because only columns 1 and 3 were marked.

Complexity

• Time: O(m·n). A constant number of passes over the matrix.
• Space: O(1) extra. Only the two booleans; all other markers live inside the matrix.

Edge cases and pitfalls

• Zero in row 0 or column 0 must be caught by the flags before any markers are written, or you lose that information.
• Clearing row 0 or column 0 too early wipes out markers that the inner pass still needs. They go last.
• Zeroing during the first scan cascades and zeroes too much. Always mark first, apply second.
• Single row or single column matrices skip the inner loops and are handled entirely by the flags.
• Using one shared marker for cell (0, 0) (it belongs to both row 0 and column 0) is a common source of bugs; separate booleans avoid it.

Related problems

• Game of Life (LeetCode 289): another in-place grid update that stores extra state inside the cells.
• Rotate Image (LeetCode 48): in-place matrix work where write order is everything.
• Product of Array Except Self (LeetCode 238): reuses the output array as scratch space to reach O(1) extra.