Set Matrix Zeroes

The trap is zeroing cells while you are still scanning for zeros — if you overwrite too early, a cell you turned into a 0 looks like a real zero to the rest of the scan and spreads incorrectly. The fix is to separate “find all the zero rows/columns” from “apply the zeroing,” using either extra sets or, for the optimal version, the matrix’s own first row and column as the storage for that information.

Track Rows/Columns with Sets

Time O(m·n)Space O(m + n)

First pass: scan the whole matrix and record which rows and which columns contain at least one zero. Second pass: zero out any cell whose row or column was flagged. Because the flagging happens entirely before any zeroing, there is no risk of a written zero being mistaken for an original one.

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == 0:
                    zero_rows.add(r)
                    zero_cols.add(c)
        for r in range(m):
            for c in range(n):
                if r in zero_rows or c in zero_cols:
                    matrix[r][c] = 0

1 / 3

comparingresultcurrent

Scan finds a zero at (1,1). Record row 1 and column 1 as needing to become zero.

Complexity: two full passes over the matrix → O(m·n) time. The sets can hold up to m row indices and n column indices → O(m + n) space.

First Row/Column as Markers

OptimalTime O(m·n)Space O(1)

Instead of separate sets, reuse matrix[0][c] and matrix[r][0] themselves as the “does this column/row need zeroing” flags — the first row and column would just get overwritten by their own logic anyway. The only wrinkle: cell (0, 0) is shared by both the first row and first column, so two separate booleans capture whether the original first row or first column contained a zero, and are applied last.

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_has_zero = any(matrix[0][c] == 0 for c in range(n))
        first_col_has_zero = any(matrix[r][0] == 0 for r in range(m))

        # use row 0 and column 0 as marker space for the rest of the grid
        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_has_zero:
            for c in range(n):
                matrix[0][c] = 0
        if first_col_has_zero:
            for r in range(m):
                matrix[r][0] = 0

Watch how the first row and column stop being data and become the storage for which rows and columns must be zeroed (marker space is ringed; trace data lives in this problem folder’s data.ts):

scan interiorfirst row zero: falsefirst col zero: falsecell: (1, 1)

Ringed cells are the first row and first column, reused as marker space.

1 / 9

comparingresultcurrent

Interior scan at (1, 1) finds a zero. Row 0 and column 0 are reserved as marker space, so this scan never touches them.

Correctness: the two booleans are captured before any markers are written, so they still describe the original first row/column. Every interior cell is only zeroed by reading markers that were fully populated in the prior pass, so the marker-writing phase and the zeroing phase never interfere with each other.

Complexity: a constant number of full passes over the matrix → O(m·n) time. No data structure grows with the input → O(1) extra space, the best possible for this problem.

Track Rows/Columns with Sets

First Row/Column as Markers

More Math & Geometry practice