Set Matrix Zeroes

Set Matrix Zeroes is a classic in-place array problem. The twist that makes it interview-worthy: doing it without allocating a second matrix. The trick is to reuse the matrix's own first row and column as bookkeeping.

The slow way first

The naive idea: scan the matrix, and whenever you hit a 0, immediately zero its row and column. This is wrong — those freshly written zeros get re-read as you keep scanning, and they cascade until the whole matrix is 0.

The fix most people reach for: remember which rows and columns contain a zero in two separate sets, then apply them in a second pass. That works and is O(m + n) extra space. But we can do better.

The idea: reuse the first row and column as flags

Instead of separate sets, store the flags inside the matrix itself. If interior cell (r, c) is 0, write a 0 into matrix[r][0] (the row flag) and matrix[0][c] (the column flag). Then a second pass zeros any interior cell whose row flag or column flag is set. No extra arrays — O(1) space.

The first row and column act as a tiny ledger riding along the edges of the data, so we never need a second copy of the grid.

Walk through it

Step through the animation. The first pass finds the 0 at (1, 1) and writes flags into matrix[1][0] and matrix[0][1]. The second pass then sweeps the interior: any cell whose row flag or column flag is set turns into 0. The flags themselves stay 0, so the border ends up correct too.

Pseudocode

rows, cols = size of matrix
# first pass: record zeros into the border
for r from 1 to rows-1:
    for c from 1 to cols-1:
        if matrix[r][c] == 0:
            matrix[r][0] = 0        # flag this row
            matrix[0][c] = 0        # flag this column
# second pass: apply the flags
for r from 1 to rows-1:
    for c from 1 to cols-1:
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0
return matrix

The Python solution

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    # second pass: apply the flags to the interior
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    return matrix

• Both loops start at index 1, leaving row 0 and column 0 free to act as flag storage.
• In the first pass, an interior 0 writes a flag into matrix[r][0] and matrix[0][c] instead of zeroing anything immediately.
• Line 11 is the heart of it: a cell is cleared if either its row flag or its column flag is set.
• The flags never get overwritten, so after the interior is done the border already holds its own correct zeros.
• A full solution also handles whether row 0 / column 0 themselves contained a zero with two boolean variables; this version focuses on the interior flag trick.

Complexity

Every version visits each cell a constant number of times, so time is O(m·n). The win here is purely on space: by borrowing the border we drop from O(m + n) auxiliary memory to a single constant.

When this pattern shows up

Practice