Loading…

mediumMath GeometryLC #73Frequently asked

Set Matrix Zeroes

Q: How do you solve Set Matrix Zeroes using the Marker Copy of the Matrix approach?

When to use it: The brute-force baseline — say it to establish correctness, then immediately note its O(mn) space is wasteful for a 2D problem. Snapshot the matrix, then use the frozen copy as the source of truth for which cells were originally zero while writing into the live matrix. **Why a copy makes correctness trivial.** The only hard part of this problem is that a zero you write looks identical to a zero that was already there. A separate, never-mutated copy removes that ambiguity entirely: you scan the copy (which still shows the original zeros), and every blanking you perform on the real matrix is driven by an original zero. No cascade is possible because the copy never gains new zeros. **Why it's the natural baseline.** It maps the english statement directly to code — 'for each original zero, clear its row and column' — with zero cleverness about storage. It's the version you can write without thinking, and stating it shows you understand the *cascade hazard* before you optimise the space away. **Why we don't ship it.** Duplicating the entire grid is O(mn) extra memory, the worst tier of the three. The interviewer will ask for better, and the path down the ladder — sets, then border flags — keeps the same correctness guarantee while shedding the copy. Time complexity: O(m·n). Space complexity: O(m·n).

Q: How do you solve Set Matrix Zeroes using the Row & Column Sets approach?

When to use it: The intermediate tier. Say 'I don't need a full copy — I only need to remember WHICH rows and columns to zero', which motivates two sets. Compress the snapshot down to just the information you actually use: which rows and which columns must be cleared. **Why two sets beat a full copy.** The marker copy stored m·n values, but the decision 'should cell (i,j) become zero?' only depends on two facts: is row i doomed, and is column j doomed? So you don't need the values — just two index sets. One pass collects every doomed row and column; a second pass blanks any cell whose row or column is in a set. That drops the memory from O(mn) to O(m+n). **Why the two passes can't be merged.** Same cascade hazard as before: if you blanked cells in the first pass, later cells in that pass would see the new zeros and over-mark. Collecting all the doomed indices *before* writing anything keeps every decision tied to the original matrix. **Why it's not yet optimal.** For a tall-and-wide matrix `O(m+n)` is small, but the follow-up explicitly asks for constant space. The final insight — that the matrix already contains m+n cells we could repurpose as these two 'sets' — is what collapses this into O(1). Time complexity: O(m·n). Space complexity: O(m + n).

Q: How do you solve Set Matrix Zeroes using the First Row / Column as Markers (Optimal, O(1) Space) approach?

When to use it: The target answer. Frame it as 'reuse the matrix's own first row and column as the two sets', and call out the (0,0) collision before you write a line. Repurpose the matrix's own border as the two marker arrays, using two booleans to resolve the cell they share. **Why the border is free storage.** The O(m+n) sets needed m row-slots and n column-slots. The matrix already owns exactly that many cells in its first column (`M[i][0]`, one per row) and first row (`M[0][j]`, one per column). Store the row flags down column 0 and the column flags along row 0, and the two 'sets' cost zero extra memory. **Why (0,0) forces two separate booleans.** Cell `M[0][0]` sits in *both* the first row and the first column, so it can't honestly represent two independent facts ('does row 0 have a zero?' and 'does column 0 have a zero?'). The fix is to pull those two facts out into standalone booleans — `firstRowZero` and `firstColZero` computed up front — and let the border cells `M[i][0]`/`M[0][j]` handle only the **interior** (i,j ≥ 1). This collision is the entire difficulty of the optimal version. **Why order of phases matters.** Apply the interior markers first (rows 1..m, cols 1..n), because the moment you zero the first row or first column you destroy the flags stored there. So: (1) record `firstRowZero`/`firstColZero`, (2) mark interior zeros into the border, (3) blank interior cells whose border flag is 0, (4) finally zero row 0 if `firstRowZero` and column 0 if `firstColZero`. Reorder these and you either lose the flags early or skip the border itself. Time complexity: O(m·n). Space complexity: O(1).

LCPractice

Math & Number Theory · 3 of 36 · 9 min

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's.

You must do it **in place**.

A naive O(mn) extra-space solution exists; a follow-up asks for an O(m + n) solution, and a true **constant-space** solution is the goal.

In plain English

Find every original zero, then blank out the full row and full column each one sits in. The subtlety is timing: you have to decide which rows and columns die based on the ORIGINAL matrix, so you can't blank them out as you go — a newly written zero would trigger more zeroing in a chain reaction.

Examples

Example 1

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Note: The single 0 at (1,1) blanks row 1 and column 1; the four corners survive.

Example 2

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Note: Zeros at (0,0) and (0,3) blank rows/columns 0 and 3; row 0 is fully zeroed, columns 0 and 3 are fully zeroed.

Example 3

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[3,4]]
Note: No zeros present, so nothing changes.

Constraints

m == matrix.length
n == matrix[0].length
1 ≤ m, n ≤ 200
-2³¹ ≤ matrix[i][j] ≤ 2³¹ − 1
Mutation must be in place; the O(1)-space solution is the target

Clarifying questions4First question: Should newly created zeros also trigger zeroing?Explore questions

Q1.Should newly created zeros also trigger zeroing?
No — only the original zeros count. That's exactly why we record positions first and mutate second; otherwise the effect cascades across the whole matrix.
Q2.What extra space am I allowed?
Start by clarifying the target. The interviewer will usually push from O(mn) to O(m+n) to O(1). I'll present the ladder and implement the constant-space version.
Q3.Is the matrix rectangular?
Yes, a clean m×n grid. The first-row/first-column flag trick relies on every row having the same length.
Q4.Can the whole matrix be zeros, or have no zeros?
Both are valid. No zeros → matrix unchanged. All zeros → stays all zeros. The algorithm must handle both without special-casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

If any cell is 0, zero out its entire row and column — in place. The trap is that zeroing as you scan corrupts the scan, so you must first record which rows/columns to clear. The progression: O(mn) marker copy → O(m+n) row/col sets → O(1) using the matrix's own first row and column as the marker storage.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise that mutating during the scan corrupts it, and whether you can climb the space ladder from O(mn) to O(1) by reusing the matrix's own first row and column as marker storage.

Where candidates slip

Zeroing rows/columns immediately on finding a 0 — the freshly written zeros are indistinguishable from originals and the whole matrix collapses to zero. Or botching the (0,0) overlap between the two flag arrays.

How to stand out

Name all three tiers, then nail the O(1) version by calling out the first-cell collision explicitly and tracking firstRow/firstCol with two independent booleans handled last.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Marker Copy of the Matrix	`O(m·n)`	`O(m·n)`	The brute-force baseline — say it to establish correctness, then immediately note its O(mn) space is wasteful for a 2D problem.	Read
2	Row & Column Sets	`O(m·n)`	`O(m + n)`	The intermediate tier. Say 'I don't need a full copy — I only need to remember WHICH rows and columns to zero', which motivates two sets.	Read
3	First Row / Column as Markers (Optimal, O(1) Space)Optimal	`O(m·n)`	`O(1)`	The target answer. Frame it as 'reuse the matrix's own first row and column as the two sets', and call out the (0,0) collision before you write a line.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewZero each 0's row and columnSpace budget?O(mn)O(m+n)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Marker Copy of the Matrix

TimeO(m·n)SpaceO(m·n)

The brute-force baseline — say it to establish correctness, then immediately note its O(mn) space is wasteful for a 2D problem.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The core problem is that zeroing changes the very cells you're still inspecting. What if you read from a frozen snapshot and write into a separate place?

2Hint 2Explore hint

Make a full copy of the matrix. Scan the copy for zeros; whenever copy[i][j] == 0, zero row i and column j in the ORIGINAL.

3Hint 3Explore hint

Because the copy never changes, every decision is based on the original zeros — no cascade.

A · Core idea

Snapshot the matrix, then use the frozen copy as the source of truth for which cells were originally zero while writing into the live matrix.

Why a copy makes correctness trivial. The only hard part of this problem is that a zero you write looks identical to a zero that was already there. A separate, never-mutated copy removes that ambiguity entirely: you scan the copy (which still shows the original zeros), and every blanking you perform on the real matrix is driven by an original zero. No cascade is possible because the copy never gains new zeros.

Why it's the natural baseline. It maps the english statement directly to code — 'for each original zero, clear its row and column' — with zero cleverness about storage. It's the version you can write without thinking, and stating it shows you understand the cascade hazard before you optimise the space away.

Why we don't ship it. Duplicating the entire grid is O(mn) extra memory, the worst tier of the three. The interviewer will ask for better, and the path down the ladder — sets, then border flags — keeps the same correctness guarantee while shedding the copy.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[1,1,1],[1,0,1],[1,1,1]]

Array state

row 1 original

contains a 0 at column 1

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[[1,0,1],[0,0,0],[1,0,1]]

C · Code with teaching comments

Reference implementation previewpublic void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] copy = new int[m][n]; for (int i = 0; i < m; i++) { copy[i] = matrix[i].clone();Explore the full code

solution.javaJava

Marker Copy of the Matrix — reference

3 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int[][] copy = new int[m][n];
4
    for (int i = 0; i < m; i++) {
5
        // Deep-copy each row so the snapshot never changes as we mutate the original.
6
        copy[i] = matrix[i].clone();
7
    }
8
    for (int i = 0; i < m; i++) {
9
        for (int j = 0; j < n; j++) {
10
            // Decision is read from the frozen copy → only original zeros trigger
11
            // blanking.
12
            if (copy[i][j] == 0) {
13
                // Zero the whole row in the live matrix; safe because we never read it
14
                // back for decisions.
15
                for (int c = 0; c < n; c++) matrix[i][c] = 0;
16
                for (int r = 0; r < m; r++) matrix[r][j] = 0;
17
            }
18
        }
19
    }
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

The copy exists purely to separate 'reading original zeros' from 'writing new zeros'. Every better approach is a cheaper way to remember which rows/columns must die without duplicating all m·n cells — first with sets, then with the matrix's own border.

ComplexityO(m·n) time, O(m·n) space — Copying is m·n cells; each zero can trigger an O(m+n) blanking but total writes are bounded by O(mn). Time O(mn); the copy is a full second grid → O(mn) space.

E · Edge cases and pitfalls4matrix = [[1,2],[3,4]] — No zeros in the copy → no blanking → matrix unchanged.Explore edge cases

Edge cases handled

matrix = [[1,2],[3,4]]No zeros in the copy → no blanking → matrix unchanged.

Pitfalls

Shallow-copying rows (copy[i] = matrix[i]) — both point to the same array, so the snapshot mutates too.
Scanning the live matrix instead of the copy — reintroduces the cascade bug.
Treating O(mn) as acceptable when the follow-up clearly wants O(1).

03.2

Approach 2 of 3

Row & Column Sets

TimeO(m·n)SpaceO(m + n)

The intermediate tier. Say 'I don't need a full copy — I only need to remember WHICH rows and columns to zero', which motivates two sets.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need every cell of the snapshot — you only need the set of row indices and the set of column indices that contain a zero.

2Hint 2Explore hint

First pass: scan the whole matrix; for each 0 at (i,j), add i to zeroRows and j to zeroCols.

3Hint 3Explore hint

Second pass: for every cell, if its row is in zeroRows or its column is in zeroCols, set it to 0.

A · Core idea

Compress the snapshot down to just the information you actually use: which rows and which columns must be cleared.

Why two sets beat a full copy. The marker copy stored m·n values, but the decision 'should cell (i,j) become zero?' only depends on two facts: is row i doomed, and is column j doomed? So you don't need the values — just two index sets. One pass collects every doomed row and column; a second pass blanks any cell whose row or column is in a set. That drops the memory from O(mn) to O(m+n).

Why the two passes can't be merged. Same cascade hazard as before: if you blanked cells in the first pass, later cells in that pass would see the new zeros and over-mark. Collecting all the doomed indices before writing anything keeps every decision tied to the original matrix.

Why it's not yet optimal. For a tall-and-wide matrix O(m+n) is small, but the follow-up explicitly asks for constant space. The final insight — that the matrix already contains m+n cells we could repurpose as these two 'sets' — is what collapses this into O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Array state

top row

zeros at columns 0 and 3 noted

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

C · Code with teaching comments

Reference implementation previewpublic void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; Set<Integer> zeroRows = new HashSet<>(); Set<Integer> zeroCols = new HashSet<>(); for (int i = 0; i < m; i++) {Explore the full code

solution.javaJava

Row & Column Sets — reference

3 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    Set<Integer> zeroRows = new HashSet<>();
4
    Set<Integer> zeroCols = new HashSet<>();
5
    for (int i = 0; i < m; i++) {
6
        for (int j = 0; j < n; j++) {
7
            // First pass only RECORDS — it never writes, so the scan stays uncorrupted.
8
            if (matrix[i][j] == 0) {
9
                // Remember the row index, not the cell value — that's the O(m+n)
10
                // compression.
11
                zeroRows.add(i);
12
                zeroCols.add(j);
13
            }
14
        }
15
    }
16
    for (int i = 0; i < m; i++) {
17
        for (int j = 0; j < n; j++) {
18
            // Second pass blanks any cell whose row OR column was doomed.
19
            if (zeroRows.contains(i) || zeroCols.contains(j)) {
20
                matrix[i][j] = 0;
21
            }
22
        }
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(m·n) timeO(m + n) spaceOpen the invariant and proofExplore the proof

The leap from the copy is realising you only need the row/column identities, not their contents — that's an O(m+n) fact, not an O(mn) one. The next leap is noticing the matrix's own first row and first column are exactly m+n spare cells that can hold those facts.

ComplexityO(m·n) time, O(m + n) space — Two full passes over m·n cells → O(mn) time. The sets hold at most m row indices and n column indices → O(m + n) space.

E · Edge cases and pitfalls5matrix = [[1,2],[3,4]] — Both sets stay empty → second pass changes nothing.Explore edge cases

Edge cases handled

matrix = [[1,2],[3,4]]Both sets stay empty → second pass changes nothing.
matrix = [[0,0],[0,0]]zeroRows={0,1}, zeroCols={0,1} → every cell zeroed (already was).

Pitfalls

Blanking inside the first pass instead of just recording — reintroduces the cascade.
Storing (i,j) pairs instead of separate row/col sets — needlessly O(number of zeros) and harder to apply.
Settling here when the follow-up explicitly wants O(1) extra space.

03.3

Approach 3 of 3 · Optimal

First Row / Column as Markers (Optimal, O(1) Space)

TimeO(m·n)SpaceO(1)

The target answer. Frame it as 'reuse the matrix's own first row and column as the two sets', and call out the (0,0) collision before you write a line.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The two sets from the previous approach need m + n slots. The matrix already HAS m + n spare cells — its first row and first column. Can you store the markers there?

2Hint 2Explore hint

Use M[i][0] as the flag for 'row i has a zero' and M[0][j] as the flag for 'column j has a zero'. But the first row and first column overlap at (0,0), so track them with two extra booleans.

3Hint 3Explore hint

Phase 1: scan firstRowZero / firstColZero separately. Phase 2: for interior cells set M[i][0] or M[0][j] to 0 on a zero. Phase 3: apply interior markers. Phase 4: zero the first row/col last, using the booleans.

A · Core idea

Repurpose the matrix's own border as the two marker arrays, using two booleans to resolve the cell they share.

Why the border is free storage. The O(m+n) sets needed m row-slots and n column-slots. The matrix already owns exactly that many cells in its first column (M[i][0], one per row) and first row (M[0][j], one per column). Store the row flags down column 0 and the column flags along row 0, and the two 'sets' cost zero extra memory.

Why (0,0) forces two separate booleans. Cell M[0][0] sits in both the first row and the first column, so it can't honestly represent two independent facts ('does row 0 have a zero?' and 'does column 0 have a zero?'). The fix is to pull those two facts out into standalone booleans — firstRowZero and firstColZero computed up front — and let the border cells M[i][0]/M[0][j] handle only the interior (i,j ≥ 1). This collision is the entire difficulty of the optimal version.

Why order of phases matters. Apply the interior markers first (rows 1..m, cols 1..n), because the moment you zero the first row or first column you destroy the flags stored there. So: (1) record firstRowZero/firstColZero, (2) mark interior zeros into the border, (3) blank interior cells whose border flag is 0, (4) finally zero row 0 if firstRowZero and column 0 if firstColZero. Reorder these and you either lose the flags early or skip the border itself.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Array state

row 0 = markers

row 0 stores column flags; (0,0) is the shared corner

(0,0) ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

C · Code with teaching comments

solution.javaJava

First Row / Column as Markers (Optimal, O(1) Space) — optimal

4 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    // Two booleans resolve the (0,0) overlap — row 0 and col 0 can't both be flagged by
4
    // the same shared cell.
5
    boolean firstRowZero = false, firstColZero = false;
6
    // Record row 0's fate up front, before the border gets repurposed as markers.
7
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
8
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;
9
    for (int i = 1; i < m; i++) {
10
        for (int j = 1; j < n; j++) {
11
            if (matrix[i][j] == 0) {
12
                // Mark row i (in column 0) and column j (in row 0) for interior zeros
13
                // only.
14
                matrix[i][0] = 0;
15
                matrix[0][j] = 0;
16
            }
17
        }
18
    }
19
    for (int i = 1; i < m; i++) {
20
        for (int j = 1; j < n; j++) {
21
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
22
                matrix[i][j] = 0;
23
            }
24
        }
25
    }
26
    // Blank the first row LAST — doing it earlier would erase the column markers stored
27
    // there.
28
    if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
29
    if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(m·n) timeO(1) spaceOpen the invariant and proofExplore the proof

The optimal trick is recognising you already own m+n spare cells — the border — and can borrow them as marker storage, paying only two booleans to untangle the one cell (0,0) that the row-array and column-array both claim. 'Reuse the input as scratch' is the canonical move whenever an O(m+n)-space grid solution is asked to become O(1).

ComplexityO(m·n) time, O(1) space — A constant number of full passes over m·n cells → O(mn) time. Only two boolean variables beyond the input → O(1) extra space.

E · Edge cases and pitfalls5matrix = [[1,0,3]] — Single row: firstRowZero=true (0 at col 1); interior loops never run; final step zeros row 0 → [[0,0,0]].Explore edge cases

Edge cases handled

matrix = [[1,0,3]]Single row: firstRowZero=true (0 at col 1); interior loops never run; final step zeros row 0 → [[0,0,0]].
matrix = [[1],[0],[3]]Single column: firstColZero=true; final step zeros column 0 → [[0],[0],[0]].

Pitfalls

Using matrix[0][0] alone to flag both row 0 and column 0 — the overlap loses one fact; you need two booleans.
Zeroing the first row/column before applying the interior markers — wipes the flags you still need to read.
Marking the border for first-row/first-column zeros (i or j == 0) instead of only the interior — corrupts the marker semantics.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic void setZeroes(int[][] matrix) { int m = matrix.length, n = matrix[0].length; boolean firstRowZero = false, firstColZero = false; for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true; for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Mutating during the scan (cascade)

If you blank a row/column the moment you see a 0, the freshly written zeros are indistinguishable from originals. Subsequent iterations treat them as triggers and the zeroing spreads until the matrix is all zeros.

Explore the code comparison

Don't write this

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            for c in range(n): matrix[i][c] = 0   # writes during scan → cascade
            for r in range(m): matrix[r][j] = 0

Write this instead

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)   # record only
for i in range(m):
    for j in range(n):
        if i in zero_rows or j in zero_cols:
            matrix[i][j] = 0

Collapsing the (0,0) flags into one cell

matrix[0][0] belongs to both the first row and the first column, so it can't independently signal 'row 0 has a zero' and 'column 0 has a zero'. Using it for both loses information and mis-zeros a border.

Explore the code comparison

Don't write this

// trying to use matrix[0][0] for both
if (rowHasZero) matrix[0][0] = 0;
if (colHasZero) matrix[0][0] = 0;   // second write hides the first fact

Write this instead

boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;

Applying the border before the interior

The first row and first column store the interior markers. If you zero them out first, you erase the flags before the interior cells get a chance to read them.

Explore the code comparison

Don't write this

if first_row_zero:
    for j in range(n): matrix[0][j] = 0   # wipes column markers too early
for i in range(1, m):
    for j in range(1, n):
        if matrix[i][0] == 0 or matrix[0][j] == 0:  # markers already gone
            matrix[i][j] = 0

Write this instead

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
if first_row_zero:
    for j in range(n): matrix[0][j] = 0

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

In-place marking using the first row/column as flags

Code pattern to memorize

firstRowZero = any 0 in row 0 ; firstColZero = any 0 in col 0
for i in 1..m, j in 1..n: if M[i][j]==0: M[i][0]=0; M[0][j]=0
for i in 1..m, j in 1..n: if M[i][0]==0 or M[0][j]==0: M[i][j]=0
if firstRowZero: zero row 0 ; if firstColZero: zero col 0

Rules to remember

1Never zero a cell while scanning — the new zeros look like original zeros and cascade, wiping the whole matrix. Mark first, mutate second.
2Use row 0 and column 0 as the marker arrays to reach O(1) space — M[i][0] flags row i, M[0][j] flags column j.
3Cell (0,0) is shared by both markers — that collision is why you need two separate booleans (firstRowZero, firstColZero) tracked independently.
4Apply the markers to the interior first (i,j ≥ 1), then handle row 0 and column 0 last, or you'll overwrite the flags before reading them.
5Three clean tiers exist (O(mn) → O(m+n) → O(1)); name all three and explain what each tier buys.

Use this pattern when

In-place grid mutation where one cell's value affects a whole row/column
Interviewer pushes from O(mn) to O(m+n) to O(1) extra space
You can repurpose existing cells (a border, a sentinel row) as scratch storage
A two-phase 'mark, then apply' pattern avoids corrupting an in-progress scan

Choose another pattern when

You're allowed a copy and clarity matters → the O(m+n) sets version is plenty
Mutation must not touch existing cells at all → you need a true copy, O(mn)
The effect is local (single cell) not row/column-wide → no marking needed
Non-rectangular / jagged input → the first-row/col flag trick assumes a clean m×n grid

Interview takeaway

When a problem demands O(1) extra space on a grid, look for storage you already own — here the matrix's own border doubles as the marker array. Reusing the input as scratch (with a couple of booleans to resolve the overlap) is the move that turns O(m+n) into O(1).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical In-Place Marking with the Input as Scratch. Recognise it whenever a grid mutation needs O(1) space and one cell affects a whole row/column — reuse the border as marker storage and split the scan into mark-then-apply phases. Same instinct as Game of Life's in-place state encoding.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rotate Image
Another in-place matrix mutation — transpose + reverse for O(1) space.
Spiral Matrix
In-place grid walk with boundary pointers — same coordinate-careful family.
Game of Life
Classic 'mutate in place without corrupting the scan' — encode old+new state in the same cell.
Special Positions in a Binary Matrix
Coming soon
Row/column aggregate counting on a matrix — precompute row and column sums.

Same pattern

←

Spiral Matrix

Continue · Next problem

Happy Number

mediumMath GeometryLC #73Frequently asked

Set Matrix Zeroes

LCPractice

Math & Number Theory · 3 of 36 · 9 min

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's.

You must do it **in place**.

A naive O(mn) extra-space solution exists; a follow-up asks for an O(m + n) solution, and a true **constant-space** solution is the goal.

In plain English

Examples

Example 1

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Note: The single 0 at (1,1) blanks row 1 and column 1; the four corners survive.

Example 2

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Note: Zeros at (0,0) and (0,3) blank rows/columns 0 and 3; row 0 is fully zeroed, columns 0 and 3 are fully zeroed.

Example 3

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[3,4]]
Note: No zeros present, so nothing changes.

Constraints

m == matrix.length
n == matrix[0].length
1 ≤ m, n ≤ 200
-2³¹ ≤ matrix[i][j] ≤ 2³¹ − 1
Mutation must be in place; the O(1)-space solution is the target

Clarifying questions4First question: Should newly created zeros also trigger zeroing?Explore questions

Q1.Should newly created zeros also trigger zeroing?
No — only the original zeros count. That's exactly why we record positions first and mutate second; otherwise the effect cascades across the whole matrix.
Q2.What extra space am I allowed?
Start by clarifying the target. The interviewer will usually push from O(mn) to O(m+n) to O(1). I'll present the ladder and implement the constant-space version.
Q3.Is the matrix rectangular?
Yes, a clean m×n grid. The first-row/first-column flag trick relies on every row having the same length.
Q4.Can the whole matrix be zeros, or have no zeros?
Both are valid. No zeros → matrix unchanged. All zeros → stays all zeros. The algorithm must handle both without special-casing.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise that mutating during the scan corrupts it, and whether you can climb the space ladder from O(mn) to O(1) by reusing the matrix's own first row and column as marker storage.

Where candidates slip

How to stand out

Name all three tiers, then nail the O(1) version by calling out the first-cell collision explicitly and tracking firstRow/firstCol with two independent booleans handled last.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Marker Copy of the Matrix	`O(m·n)`	`O(m·n)`	The brute-force baseline — say it to establish correctness, then immediately note its O(mn) space is wasteful for a 2D problem.	Read
2	Row & Column Sets	`O(m·n)`	`O(m + n)`	The intermediate tier. Say 'I don't need a full copy — I only need to remember WHICH rows and columns to zero', which motivates two sets.	Read
3	First Row / Column as Markers (Optimal, O(1) Space)Optimal	`O(m·n)`	`O(1)`	The target answer. Frame it as 'reuse the matrix's own first row and column as the two sets', and call out the (0,0) collision before you write a line.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Marker Copy of the Matrix

TimeO(m·n)SpaceO(m·n)

The brute-force baseline — say it to establish correctness, then immediately note its O(mn) space is wasteful for a 2D problem.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The core problem is that zeroing changes the very cells you're still inspecting. What if you read from a frozen snapshot and write into a separate place?

2Hint 2Explore hint

Make a full copy of the matrix. Scan the copy for zeros; whenever copy[i][j] == 0, zero row i and column j in the ORIGINAL.

3Hint 3Explore hint

Because the copy never changes, every decision is based on the original zeros — no cascade.

A · Core idea

Snapshot the matrix, then use the frozen copy as the source of truth for which cells were originally zero while writing into the live matrix.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[1,1,1],[1,0,1],[1,1,1]]

Array state

row 1 original

contains a 0 at column 1

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result[[1,0,1],[0,0,0],[1,0,1]]

C · Code with teaching comments

solution.javaJava

Marker Copy of the Matrix — reference

3 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    int[][] copy = new int[m][n];
4
    for (int i = 0; i < m; i++) {
5
        // Deep-copy each row so the snapshot never changes as we mutate the original.
6
        copy[i] = matrix[i].clone();
7
    }
8
    for (int i = 0; i < m; i++) {
9
        for (int j = 0; j < n; j++) {
10
            // Decision is read from the frozen copy → only original zeros trigger
11
            // blanking.
12
            if (copy[i][j] == 0) {
13
                // Zero the whole row in the live matrix; safe because we never read it
14
                // back for decisions.
15
                for (int c = 0; c < n; c++) matrix[i][c] = 0;
16
                for (int r = 0; r < m; r++) matrix[r][j] = 0;
17
            }
18
        }
19
    }
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4matrix = [[1,2],[3,4]] — No zeros in the copy → no blanking → matrix unchanged.Explore edge cases

Edge cases handled

matrix = [[1,2],[3,4]]No zeros in the copy → no blanking → matrix unchanged.

Pitfalls

Shallow-copying rows (copy[i] = matrix[i]) — both point to the same array, so the snapshot mutates too.
Scanning the live matrix instead of the copy — reintroduces the cascade bug.
Treating O(mn) as acceptable when the follow-up clearly wants O(1).

03.2

Approach 2 of 3

Row & Column Sets

TimeO(m·n)SpaceO(m + n)

The intermediate tier. Say 'I don't need a full copy — I only need to remember WHICH rows and columns to zero', which motivates two sets.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't need every cell of the snapshot — you only need the set of row indices and the set of column indices that contain a zero.

2Hint 2Explore hint

First pass: scan the whole matrix; for each 0 at (i,j), add i to zeroRows and j to zeroCols.

3Hint 3Explore hint

Second pass: for every cell, if its row is in zeroRows or its column is in zeroCols, set it to 0.

A · Core idea

Compress the snapshot down to just the information you actually use: which rows and which columns must be cleared.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Array state

top row

zeros at columns 0 and 3 noted

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

C · Code with teaching comments

solution.javaJava

Row & Column Sets — reference

3 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    Set<Integer> zeroRows = new HashSet<>();
4
    Set<Integer> zeroCols = new HashSet<>();
5
    for (int i = 0; i < m; i++) {
6
        for (int j = 0; j < n; j++) {
7
            // First pass only RECORDS — it never writes, so the scan stays uncorrupted.
8
            if (matrix[i][j] == 0) {
9
                // Remember the row index, not the cell value — that's the O(m+n)
10
                // compression.
11
                zeroRows.add(i);
12
                zeroCols.add(j);
13
            }
14
        }
15
    }
16
    for (int i = 0; i < m; i++) {
17
        for (int j = 0; j < n; j++) {
18
            // Second pass blanks any cell whose row OR column was doomed.
19
            if (zeroRows.contains(i) || zeroCols.contains(j)) {
20
                matrix[i][j] = 0;
21
            }
22
        }
23
    }
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(m·n) timeO(m + n) spaceOpen the invariant and proofExplore the proof

ComplexityO(m·n) time, O(m + n) space — Two full passes over m·n cells → O(mn) time. The sets hold at most m row indices and n column indices → O(m + n) space.

E · Edge cases and pitfalls5matrix = [[1,2],[3,4]] — Both sets stay empty → second pass changes nothing.Explore edge cases

Edge cases handled

matrix = [[1,2],[3,4]]Both sets stay empty → second pass changes nothing.
matrix = [[0,0],[0,0]]zeroRows={0,1}, zeroCols={0,1} → every cell zeroed (already was).

Pitfalls

Blanking inside the first pass instead of just recording — reintroduces the cascade.
Storing (i,j) pairs instead of separate row/col sets — needlessly O(number of zeros) and harder to apply.
Settling here when the follow-up explicitly wants O(1) extra space.

03.3

Approach 3 of 3 · Optimal

First Row / Column as Markers (Optimal, O(1) Space)

TimeO(m·n)SpaceO(1)

The target answer. Frame it as 'reuse the matrix's own first row and column as the two sets', and call out the (0,0) collision before you write a line.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The two sets from the previous approach need m + n slots. The matrix already HAS m + n spare cells — its first row and first column. Can you store the markers there?

2Hint 2Explore hint

Use M[i][0] as the flag for 'row i has a zero' and M[0][j] as the flag for 'column j has a zero'. But the first row and first column overlap at (0,0), so track them with two extra booleans.

3Hint 3Explore hint

A · Core idea

Repurpose the matrix's own border as the two marker arrays, using two booleans to resolve the cell they share.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

Array state

row 0 = markers

row 0 stores column flags; (0,0) is the shared corner

(0,0) ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

C · Code with teaching comments

solution.javaJava

First Row / Column as Markers (Optimal, O(1) Space) — optimal

4 teaching notes

1
public void setZeroes(int[][] matrix) {
2
    int m = matrix.length, n = matrix[0].length;
3
    // Two booleans resolve the (0,0) overlap — row 0 and col 0 can't both be flagged by
4
    // the same shared cell.
5
    boolean firstRowZero = false, firstColZero = false;
6
    // Record row 0's fate up front, before the border gets repurposed as markers.
7
    for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
8
    for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;
9
    for (int i = 1; i < m; i++) {
10
        for (int j = 1; j < n; j++) {
11
            if (matrix[i][j] == 0) {
12
                // Mark row i (in column 0) and column j (in row 0) for interior zeros
13
                // only.
14
                matrix[i][0] = 0;
15
                matrix[0][j] = 0;
16
            }
17
        }
18
    }
19
    for (int i = 1; i < m; i++) {
20
        for (int j = 1; j < n; j++) {
21
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
22
                matrix[i][j] = 0;
23
            }
24
        }
25
    }
26
    // Blank the first row LAST — doing it earlier would erase the column markers stored
27
    // there.
28
    if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
29
    if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(m·n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(m·n) time, O(1) space — A constant number of full passes over m·n cells → O(mn) time. Only two boolean variables beyond the input → O(1) extra space.

E · Edge cases and pitfalls5matrix = [[1,0,3]] — Single row: firstRowZero=true (0 at col 1); interior loops never run; final step zeros row 0 → [[0,0,0]].Explore edge cases

Edge cases handled

matrix = [[1,0,3]]Single row: firstRowZero=true (0 at col 1); interior loops never run; final step zeros row 0 → [[0,0,0]].
matrix = [[1],[0],[3]]Single column: firstColZero=true; final step zeros column 0 → [[0],[0],[0]].

Pitfalls

Using matrix[0][0] alone to flag both row 0 and column 0 — the overlap loses one fact; you need two booleans.
Zeroing the first row/column before applying the interior markers — wipes the flags you still need to read.
Marking the border for first-row/first-column zeros (i or j == 0) instead of only the interior — corrupts the marker semantics.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Mutating during the scan (cascade)

Explore the code comparison

Don't write this

for i in range(m):
    for j in range(n):
        if matrix[i][j] == 0:
            for c in range(n): matrix[i][c] = 0   # writes during scan → cascade
            for r in range(m): matrix[r][j] = 0

Write this instead

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)   # record only
for i in range(m):
    for j in range(n):
        if i in zero_rows or j in zero_cols:
            matrix[i][j] = 0

Collapsing the (0,0) flags into one cell

Explore the code comparison

Don't write this

// trying to use matrix[0][0] for both
if (rowHasZero) matrix[0][0] = 0;
if (colHasZero) matrix[0][0] = 0;   // second write hides the first fact

Write this instead

boolean firstRowZero = false, firstColZero = false;
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;

Applying the border before the interior

The first row and first column store the interior markers. If you zero them out first, you erase the flags before the interior cells get a chance to read them.

Explore the code comparison

Don't write this

if first_row_zero:
    for j in range(n): matrix[0][j] = 0   # wipes column markers too early
for i in range(1, m):
    for j in range(1, n):
        if matrix[i][0] == 0 or matrix[0][j] == 0:  # markers already gone
            matrix[i][j] = 0

Write this instead

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
if first_row_zero:
    for j in range(n): matrix[0][j] = 0

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

In-place marking using the first row/column as flags

Code pattern to memorize

firstRowZero = any 0 in row 0 ; firstColZero = any 0 in col 0
for i in 1..m, j in 1..n: if M[i][j]==0: M[i][0]=0; M[0][j]=0
for i in 1..m, j in 1..n: if M[i][0]==0 or M[0][j]==0: M[i][j]=0
if firstRowZero: zero row 0 ; if firstColZero: zero col 0

Rules to remember

1Never zero a cell while scanning — the new zeros look like original zeros and cascade, wiping the whole matrix. Mark first, mutate second.
2Use row 0 and column 0 as the marker arrays to reach O(1) space — M[i][0] flags row i, M[0][j] flags column j.
3Cell (0,0) is shared by both markers — that collision is why you need two separate booleans (firstRowZero, firstColZero) tracked independently.
4Apply the markers to the interior first (i,j ≥ 1), then handle row 0 and column 0 last, or you'll overwrite the flags before reading them.
5Three clean tiers exist (O(mn) → O(m+n) → O(1)); name all three and explain what each tier buys.

Use this pattern when

In-place grid mutation where one cell's value affects a whole row/column
Interviewer pushes from O(mn) to O(m+n) to O(1) extra space
You can repurpose existing cells (a border, a sentinel row) as scratch storage
A two-phase 'mark, then apply' pattern avoids corrupting an in-progress scan

Choose another pattern when

You're allowed a copy and clarity matters → the O(m+n) sets version is plenty
Mutation must not touch existing cells at all → you need a true copy, O(mn)
The effect is local (single cell) not row/column-wide → no marking needed
Non-rectangular / jagged input → the first-row/col flag trick assumes a clean m×n grid

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rotate Image
Another in-place matrix mutation — transpose + reverse for O(1) space.
Spiral Matrix
In-place grid walk with boundary pointers — same coordinate-careful family.
Game of Life
Classic 'mutate in place without corrupting the scan' — encode old+new state in the same cell.
Special Positions in a Binary Matrix
Coming soon
Row/column aggregate counting on a matrix — precompute row and column sums.

Same pattern

←

Spiral Matrix

Continue · Next problem

Happy Number