Skip to content

Volume ITechnology

4.28.3 — Set Matrix Zeroes ​

LeetCode 73 · Medium

The problem ​

If any cell is 0, set its entire row and column to 0. Do it in place.

1 1 1        1 0 1
1 0 1   →    0 0 0
1 1 1        1 0 1

The follow-up asks for O(1) extra space.

Restating the Problem: You are given an m \times n matrix. If any cell has the value 0, you must change its entire row and its entire column to 0.

  • Constraints to note: m, n \le 200.
  • Edge cases: The first row or column might contain a zero originally, which requires careful tracking if we plan to use them as storage.

Why the naive version is wrong ​

Setting rows and columns to zero as you find zeros corrupts the input as you read it — a zero you just wrote is indistinguishable from a zero that was there originally, so it triggers more clearing, and eventually the whole matrix is zero.

So you must record everything first, then apply. Two passes, always.

The easy version keeps two sets of the rows and columns to clear — O(m + n) space — and that is a perfectly good first answer.

The O(1)-space idea ​

Use the matrix's own first row and first column as the record.

If matrix[r][c] is 0, write a 0 into matrix[r][0] and matrix[0][c]. Those marks live inside the matrix, so no extra memory is used — and both cells are going to be zeroed anyway, so nothing is lost.

Except for one collision, and it is the whole difficulty.

matrix[0][0] would have to record both "clear row 0" and "clear column 0", and it can only hold one.

The fix is a single extra boolean. Handle the first column with its own flag, and let matrix[0][0] mean "clear row 0".

The four passes ​

  1. Scan the first column. If any cell is 0, remember it in first_col_zero.
  2. Scan the rest of the matrix, from row 0 and column 1. Mark zeros in matrix[r][0] and matrix[0][c].
  3. Apply, from the inside out. Walk rows 1 onward and columns 1 onward, zeroing any cell whose row or column marker is 0.
  4. Apply the first row and first column last, using matrix[0][0] and first_col_zero.

Pass 3 must go before pass 4. If you cleared the first row first, its markers would be destroyed before the inner cells had used them. Order is the correctness argument for this whole solution.

The solution ​

python
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])
        first_col_zero = False  # (1)

        # 1 & 2: record, using row 0 and column 0 as the markers
        for r in range(rows):  # (2)
            if matrix[r][0] == 0:  # (3)
                first_col_zero = True                  # column 0 needs clearing

            for c in range(1, cols):                   # (4) start at 1, not 0
                if matrix[r][c] == 0:
                    matrix[r][0] = 0  # (5)
                    matrix[0][c] = 0

        # 3: apply to the interior, bottom-right first is not required — but
        #    the first row and column must not be cleared yet
        for r in range(1, rows):  # (6)
            for c in range(1, cols):
                if matrix[r][0] == 0 or matrix[0][c] == 0:  # (7)
                    matrix[r][c] = 0

        # 4a: the first row, decided by matrix[0][0]
        if matrix[0][0] == 0:  # (8)
            for c in range(cols):
                matrix[0][c] = 0

        # 4b: the first column, decided by the flag
        if first_col_zero:  # (9)
            for r in range(rows):
                matrix[r][0] = 0
ts
function setZeroes(matrix: number[][]): void {
  const rows = matrix.length, cols = matrix[0].length;
  let firstColZero = false;  // (1)

  for (let r = 0; r < rows; r++) {  // (2)
    if (matrix[r][0] === 0) firstColZero = true;  // (3)
    for (let c = 1; c < cols; c++) {  // (4)
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;  // (5)
        matrix[0][c] = 0;
      }
    }
  }

  for (let r = 1; r < rows; r++) {  // (6)
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;  // (7)
    }
  }

  if (matrix[0][0] === 0) {  // (8)
    for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  }

  if (firstColZero) {  // (9)
    for (let r = 0; r < rows; r++) matrix[r][0] = 0;
  }
}

Line by line ​

The idea is to use the grid's own first row and first column as notepads. matrix[0][c] = 0 will mean "column c must be cleared", and matrix[r][0] = 0 will mean "row r must be cleared". The cell matrix[0][0] sits in both, so it can only mean one thing. We let it mean "row 0 must be cleared", and keep a separate flag for column 0.

(1) The extra flag: does column 0 need clearing?

(2) Pass one: look at every row.

(3) A zero in column 0 means column 0 must be cleared. Set the flag rather than writing anywhere.

(4) Look at the other columns of this row, from 1 onward. Column 0 is the notepad, so it is not checked here.

(5) A zero at (r, c) means row r and column c must be cleared. Write that into the two notepads.

(6) Pass two: clear the inside of the grid, every cell not in row 0 or column 0. The notepads must stay untouched until this is done, because they are still being read.

(7) Clear a cell if its row or its column was marked.

(8) Now handle row 0, using matrix[0][0].

(9) Last, handle column 0, using the flag. Column 0 is cleared after row 0 on purpose: clearing it first would set matrix[0][0] to 0, and line (8) would then wrongly clear row 0.

Code Walkthrough (O(1) Space):

  • Pass 1 (Flag Column 0): We scan the first column (matrix[r][0]). If we find any zero, we set first_col_zero = True.
  • Pass 2 (Record in Margins): We scan the rest of the matrix (rows 0 \dots m-1, columns 1 \dots n-1). If matrix[r][c] == 0, we write a 0 to the top of its column (matrix[0][c]) and the start of its row (matrix[r][0]).
  • Pass 3 (Apply to Interior): We scan the interior again (rows 1 \dots m-1, columns 1 \dots n-1). If either its row's marker (matrix[r][0]) or its column's marker (matrix[0][c]) is 0, we set matrix[r][c] = 0.
  • Pass 4 (Apply to Margins):
    • If matrix[0][0] == 0, we clear the entire first row.
    • If first_col_zero is True, we clear the entire first column.

The inner loop of pass 1 starts at column 1. Column 0 is handled by the flag, so reading it as a normal cell would confuse the two roles.

matrix[0][0] means "clear row 0", and the separate flag means "clear column 0". Splitting the two meanings is the entire trick.

Pass 3 runs before pass 4, so the markers survive until they have been used.

Trace ​

0 1 2 0
3 4 5 2
1 3 1 5

Pass 1: matrix[0][0] is 0 → first_col_zero = True. The 0 at (0,3) sets matrix[0][0] = 0 (already) and matrix[0][3] = 0 (already).

After recording, row 0 is 0 1 2 0, and no other row has a zero in columns 1 onward.

Pass 3: for r in 1..2, c in 1..3 — clear where matrix[r][0] == 0 (no) or matrix[0][c] == 0 (true for c = 3). So (1,3) and (2,3) become 0.

Pass 4a: matrix[0][0] is 0 → clear all of row 0.

Pass 4b: flag is true → clear all of column 0.

0 0 0 0
0 4 5 0
0 3 1 0

✓

Edge cases ​

  • A zero at (0, 0). It clears both row 0 (through matrix[0][0]) and column 0 (through the flag).
  • No zeros. Nothing changes.
  • A zero in the first row only. Line (5) marks its column and row 0, and both are cleared.

Complexity ​

O(mn) time, O(1) extra space.

  • Time Complexity: O(mn). We pass over the matrix multiple times (recording, applying to interior, applying to margins), but it is a constant number of passes over m \times n elements.
  • Space Complexity: O(1). We use one boolean variable (first_col_zero) and repurpose the input matrix's first row and column as our state storage, requiring no additional arrays.

The set-based version is O(m + n) space and much easier to write.

Which to write ​

Write the O(m+n) version first, say its space cost, then offer this one when the follow-up comes. It is short:

python
zero_rows = {r for r in range(rows) for c in range(cols) if matrix[r][c] == 0}
zero_cols = {c for r in range(rows) for c in range(cols) if matrix[r][c] == 0}
for r in range(rows):
    for c in range(cols):
        if r in zero_rows or c in zero_cols:
            matrix[r][c] = 0

The O(1) version is not better in any practical sense — O(m + n) is tiny — so its value is entirely as a demonstration that you can use the data structure itself as scratch space. Say that honestly rather than pretending it matters.

Where this goes next ​

The idea — store state inside the data you already have — recurs:

  • Find the Duplicate Number by negating nums[abs(x)] as a visited flag, when mutation is allowed. 4.9.8.
  • First Missing Positive — place each value at its own index, using the array as its own hash table.
  • Number of Islands — the grid is the visited set. 4.20.1.
  • Copy List with Random Pointer — weaving copies into the original list. 4.9.5.

Every one of them trades clarity for memory, and every one of them mutates the input — which is a real cost outside a coding judge.

What the interviewer will push on ​

"Why can't you clear as you scan?" Written zeros are indistinguishable from original ones, so the clearing cascades.

"Where do you store the markers, and what collides?" The first row and column, and matrix[0][0] has two jobs — hence the extra flag.

"Why must the interior be cleared before the first row and column?" Otherwise the markers are destroyed before use.

"Is O(1) space actually worth it here?" Honestly, no — O(m+n) is negligible. Say so; it shows judgement rather than reflex.

One thing to volunteer: name the collision at matrix[0][0] before writing any code. It is the only genuinely hard part, and stating it first makes the four passes look inevitable.

Next: 4.28.4 Happy Number — cycle detection somewhere you would not expect it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet