Set Matrix Zeroes — InterviewPrepKit

Solving tips

Spot the cascade trap: separate a detect pass (find all original zeros) from an apply pass, or written zeros will trigger extra clearing.
For O(1) space, reuse the first row and first column as marker arrays; track whether row 0 and col 0 themselves need clearing with two separate boolean flags.
Target O(m*n) time and O(1) extra space (the two flags are the only auxiliary storage).
Common pitfall: compute the first-row/first-col flags before the inner marking overwrites (0,0), and clear the first row/column LAST since the markers live there.

Problem

You are given an m x n integer matrix. If any cell contains 0, set that cell’s entire row and entire column to 0. Do it in place, mutating the given matrix.

The subtlety: the zeroing must be based on the original positions of the zeros. A zero you write during the process must not trigger further rows/columns to be cleared.

Examples

[[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]] — the single 0 at (1,1) clears row 1 and column 1.
[[0,1,2,0],[3,4,5,2],[1,3,1,5]] → [[0,0,0,0],[0,4,5,0],[0,3,1,0]] — zeros in row 0 clear columns 0 and 3, and row 0 itself.
[[1,2,3],[4,5,6]] → [[1,2,3],[4,5,6]] — no zeros, nothing changes.

Constraints

m == len(matrix), n == len(matrix[0])
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1
Follow-ups: an O(m·n) space solution is trivial; O(m + n) is better; the target is a constant-space solution.

Think about it first

Hint 1

The danger is cascading: if you zero a row as soon as you see a `0`, later cells in that row look like original zeros. So first *find* all the zeros, then *apply* the clearing in a second phase.

Hint 2

Remembering which rows and which columns must be cleared needs only two sets (or two boolean arrays) of size `m` and `n` — that's O(m + n) space, independent of how many zeros there are.

Hint 3

To reach O(1) space, store those row/column flags *inside the matrix itself*: use the first row and first column as marker arrays. Handle the first row and first column specially with a couple of standalone boolean flags, because they overlap at cell `(0,0)`.

TL;DR

Use the first row and first column as marker arrays (plus two flags) to zero rows/columns in place — O(m·n) time, O(1) extra space.

Approach 1 — Naive: record rows and columns in sets

The intuition first. The only correctness trap is cascading — a zero you write must not cause more clearing. Avoid it by separating detection from action: first scan the whole matrix and remember every row index and column index that contains an original zero; then clear.

from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        zero_rows, zero_cols = set(), set()

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zero_rows.add(i)
                    zero_cols.add(j)

        for i in range(m):
            for j in range(n):
                if i in zero_rows or j in zero_cols:
                    matrix[i][j] = 0

Complexity: O(m·n) time, O(m + n) extra space for the two sets.

Correct and readable. The remaining challenge — the classic follow-up — is doing it without those auxiliary sets.

Approach 2 — Markers in the first row and column (O(1) space)

The insight: we already have space to store the row/column flags — inside the matrix. Let cell (i, 0) remember “row i must be cleared” and cell (0, j) remember “column j must be cleared.” The only conflict is the overlap: the first row and first column share cell (0,0) and are themselves data. So we track those two with separate boolean flags and process the first row/column last.

from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        first_row_zero = any(matrix[0][j] == 0 for j in range(n))
        first_col_zero = any(matrix[i][0] == 0 for i in range(m))

        # use row 0 and column 0 as marker arrays for the inner cells
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # clear inner cells based on the markers
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        # finally clear the first row / column if flagged
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0

Walkthrough with [[0,1,2,0],[3,4,5,2],[1,3,1,5]] (m=3, n=4):

Scan first row → contains zeros (0 at cols 0 and 3) → first_row_zero = True. First column has 0 at (0,0) → first_col_zero = True.
Mark inner cells (rows/cols ≥ 1): no inner zeros exist here, so the markers set by the inner scan come only from row 0 / col 0 already being 0.
Apply markers to inner cells: column 3’s marker matrix[0][3] = 0 clears (1,3) and (2,3); column 0’s marker matrix[0][0] = 0 clears (1,0) and (2,0). Grid so far: [[0,1,2,0],[0,4,5,0],[0,3,1,0]].
first_row_zero → clear row 0 fully: [0,0,0,0]. first_col_zero → clear column 0 (already 0).
Final: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]. Matches the expected output.

Complexity: O(m·n) time, O(1) extra space — the two boolean flags are the only auxiliary storage.

Common pitfalls

Clearing a row/column the instant you see a 0, which cascades and zeroes cells that were originally nonzero. Always detect first, apply second.
Forgetting the two overlap flags for the first row and first column, or computing them after the inner scan has already overwritten (0,0).
Processing the first row/column before the inner cells — the markers live there, so wipe them last.
Using matrix[0][0] alone to encode both first-row and first-column state without a second flag; one cell can’t safely represent both.

Pattern takeaway

When a problem forbids extra space, look for slack inside the input itself: reusing the border row and column as bookkeeping arrays is the canonical trick. The general recipe — separate a detect pass from an apply pass, and stash flags in cells you’ll process last — recurs across in-place grid problems.