73. Set Matrix Zeroes

MediumMatrix and SimulationIn-place flag encodingFirst row/column as marker storage

Set Matrix Zeroes

Given an m x n integer matrix, if any cell is 0 set its entire row and entire column to 0. Do it in place, using O(1) extra space (no separate m+n marker arrays).

Open official problem prompt ↗

In plain English

Blank out every row and column that touches a zero, changing the grid directly without proportional extra memory.

Picture it like this

Like using the margins of a spreadsheet to jot which rows and columns to erase, instead of grabbing a separate notepad.

Example

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Why: The single 0 sits at row 1, column 1, so that whole row and column become 0 while the rest is unchanged.

Constraints

m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1

Pattern lesson

See the pattern, then code

First row/column as marker storage

↗

Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. You need to remember which rows and columns must be zeroed without extra arrays. The first row and first column can serve as those marker arrays, provided you separately record whether the first row or first column themselves originally contained a zero.

New words, made simpleKnow these before the algorithm

Marker cell: A first-row or first-column cell set to 0 to remember that its column or row must be zeroed.
In-place: Modifying the matrix itself with only constant extra variables.
Two-pass: One sweep to record markers, a second sweep to apply them.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Collect zero positions in sets

Simple but uses extra space, failing the O(1) follow-up.

Record all zero rows and columns in two hash sets, then blank them.

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

Best choiceFirst row/column as markers

Meets the constant-space requirement.

Store markers inside the matrix's own border, guarded by two booleans for the border itself.

Time O(m*n)Space O(1)

The rule we keep true

Invariant

After the marking pass, matrix[i][0]==0 means row i must be zeroed and matrix[0][j]==0 means column j must be zeroed, while the two booleans independently record the border's own fate.

Why this is correct

Reasoning

The border cells are read as markers only for inner cells, so overwriting them does not corrupt inner decisions. Because the first row and first column are decided by the pre-computed booleans and applied last, the markers can be safely reused before being overwritten themselves.

The algorithm in three movesSay these aloud before coding

1Record with two booleans whether the first row and first column contain any zero

first_row_zero=False, first_col_zero=False

2For each inner cell that is 0, mark matrix[i][0] and matrix[0][j] to 0

cell(1,1)=0 -> mark (1,0)=0 and (0,1)=0

3Zero every inner cell whose row marker or column marker is 0

zero inner cells where marker set

4Finally zero the first row and/or first column if their booleans were set

apply first row/col if flagged

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readrow 0 and col 0

2 · AskAny zero on border?

3 · Update statefirst_row_zero=False, first_col_zero=False

4 · Resultborder originally has no zero

Key takeaway

The single zero at center (index 4) triggers zeroing of its row and column.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-5Snapshot the border
Booleans capture whether the first row/column must be zeroed, because their cells will be overwritten by markers.
2
Lines 6-11Marking pass
Every inner zero stamps its row marker and column marker onto the border.
3
Lines 12-15Application pass
Inner cells are zeroed whenever their row or column marker is set.
4
Lines 16-21Finish the border
Applied last so it cannot disturb the markers earlier passes relied on.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A zero located in the first row or first column
A single row or single column matrix
A matrix already full of zeros
A matrix with no zeros at all (unchanged)

Common beginner mistakes

Applying the first row/column before finishing inner cells, which spreads spurious zeros through the markers
Forgetting the two boolean snapshots and losing the original border state
Iterating inner ranges from 0 instead of 1 and reading a marker as real data

Check your understanding

Why must you record first_row_zero and first_col_zero before the marking pass?

PyPython 3 · solution.py

Optimal

1class Solution:2    def setZeroes(self, matrix: list[list[int]]) -> None:3        m, n = len(matrix), len(matrix[0])4        first_row_zero = any(matrix[0][j] == 0 for j in range(n))5        first_col_zero = any(matrix[i][0] == 0 for i in range(m))6        for i in range(1, m):7            for j in range(1, n):8                if matrix[i][j] == 0:9                    matrix[i][0] = 010                    matrix[0][j] = 011        for i in range(1, m):12            for j in range(1, n):13                if matrix[i][0] == 0 or matrix[0][j] == 0:14                    matrix[i][j] = 015        if first_row_zero:16            for j in range(n):17                matrix[0][j] = 018        if first_col_zero:19            for i in range(m):20                matrix[i][0] = 0

Time complexityO(m*n)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftMeta

Set Matrix Zeroes

Set Matrix Zeroes

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Matrix and Simulation