Set Matrix Zeroes: In-Place Matrix Marking

You are given an m x n integer matrix. If any element is zero, set its entire row and column to zero. Do it in place.

That is LeetCode 73: Set Matrix Zeroes. The brute force is straightforward, but the real challenge is doing it without allocating extra space proportional to the matrix size. The O(1) space solution uses a clever trick: the matrix's own first row and first column become the marker arrays.

Original matrix

→

↓

First row/col as markers

→

↓

Result

Why this problem matters

Set matrix zeroes is one of the most popular in-place matrix problems in interviews. It tests whether you can use existing data structures as auxiliary storage instead of reaching for extra memory. The core idea, repurposing part of the input as bookkeeping space, shows up across many problems: from in-place array deduplication to cycle detection in linked lists.

The problem also forces you to think carefully about order of operations. If you zero the markers too early, you corrupt the information you need to process the rest of the matrix. Getting the sequencing right is where most people trip up.

The key insight

When you find a zero at position (r, c), you need to remember "row r should be zeroed" and "column c should be zeroed." The naive approach uses separate sets for this. But the matrix already has a natural place to store these flags: the first row and first column.

For each zero at (r, c), set matrix[r][0] = 0 (marking the row) and matrix[0][c] = 0 (marking the column). Then make a second pass through the matrix, zeroing any cell whose row or column is marked.

There is one catch: the first row and first column overlap at matrix[0][0]. You cannot use that single cell to track both "should the first row be zeroed?" and "should the first column be zeroed?" So you use a separate boolean for one of them (typically the first column), and let matrix[0][0] handle the first row.

Approach 1: Brute force with a copy - O(mn) space

The simplest approach: copy the entire matrix, then scan the copy for zeroes and zero the corresponding rows and columns in the original.

def set_zeroes(matrix: list[list[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    copy = [row[:] for row in matrix]

    for r in range(m):
        for c in range(n):
            if copy[r][c] == 0:
                # Zero the entire row
                for j in range(n):
                    matrix[r][j] = 0
                # Zero the entire column
                for i in range(m):
                    matrix[i][c] = 0

This works but uses O(mn) extra space for the copy. We can do better.

Approach 2: Row and column sets - O(m+n) space

Instead of copying the whole matrix, just record which rows and columns need to be zeroed.

def set_zeroes(matrix: list[list[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    zero_rows = set()
    zero_cols = set()

    # First pass: find all zeroes
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)

    # Second pass: zero marked rows and columns
    for r in range(m):
        for c in range(n):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0

O(m + n) space for the two sets. This is a solid answer in interviews, but the follow-up asks: can you do it in O(1) space?

Approach 3: First row/column as markers - O(1) space

Here is the optimal solution. Instead of allocating separate sets, use the first row and first column of the matrix itself to store the zero flags.

def set_zeroes(matrix: list[list[int]]) -> None:
    m, n = len(matrix), len(matrix[0])
    first_col_zero = False

    # Step 1: scan and mark
    for r in range(m):
        if matrix[r][0] == 0:
            first_col_zero = True
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    # Step 2: zero inner cells using markers
    for r in range(m - 1, 0, -1):
        for c in range(n - 1, 0, -1):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    # Step 3: zero the first row if needed
    if matrix[0][0] == 0:
        for c in range(n):
            matrix[0][c] = 0

    # Step 4: zero the first column if needed
    if first_col_zero:
        for r in range(m):
            matrix[r][0] = 0

Let's walk through each step.

Step 1: Scan and mark. We iterate through every cell. When we find a zero at (r, c), we set matrix[r][0] = 0 (mark the row in the first column) and matrix[0][c] = 0 (mark the column in the first row). We also track whether the first column itself originally contained a zero using the first_col_zero boolean.

Why do we need first_col_zero? Because matrix[0][0] is shared between the first row and the first column. We let matrix[0][0] mean "the first row needs to be zeroed." For the first column, we use the separate boolean.

Step 2: Zero the inner cells. We iterate backward through rows m-1 down to 1 and columns n-1 down to 1. If the row marker (matrix[r][0]) or the column marker (matrix[0][c]) is zero, we set the cell to zero. We go backward to avoid corrupting the markers in the first row and column before we are done using them.

Step 3: Zero the first row. If matrix[0][0] == 0, the first row had a zero (either originally or because some column was marked). Zero the entire first row.

Step 4: Zero the first column. If first_col_zero is true, the first column originally contained a zero. Zero the entire first column.

The order of steps 3 and 4 matters. We must handle the inner cells before the first row and column, otherwise we would destroy our markers prematurely.

Visual walkthrough

Let's trace through a 4x4 matrix with zeroes at positions (1,1) and (2,3).

The key thing to notice is how the first row and first column act as compressed storage for the row and column sets from Approach 2. Instead of allocating O(m + n) extra memory, we borrow space that is already there.

Complexity analysis

Time: Two passes through the matrix. The first pass scans for zeroes and sets markers. The second pass zeroes cells based on markers. Both are O(m * n).

Space: One boolean variable (first_col_zero). Everything else is stored in the matrix itself. That is O(1) extra space.

Edge cases

• No zeroes: the matrix is unchanged. The marking pass finds nothing, and the zeroing pass has nothing to act on.
• Entire matrix is zeroes: every row and column gets marked. The result is all zeroes (same as input).
• Zero in the first row or first column: this is exactly why we need the first_col_zero boolean and the separate handling in steps 3 and 4. Without them, we would not know whether a zero in matrix[0][0] was original or placed there as a marker.
• Single row or single column: the algorithm still works. The inner loop just has nothing to do, and the first-row/first-column cleanup handles everything.
• 1x1 matrix: [[0]] stays [[0]], and [[5]] stays [[5]].

Common mistakes

1. Zeroing cells during the scan pass. If you set cells to zero while still scanning for original zeroes, newly zeroed cells trigger false positives. Always separate the marking pass from the zeroing pass.

2. Using matrix[0][0] for both the first row and first column. This single cell cannot carry two flags. Use a separate variable for one of them.

3. Iterating forward during the zeroing pass. If you zero the first row or column before processing inner cells, you destroy the markers you still need. Process inner cells first, then handle the first row and column.

4. Forgetting to handle the first column separately. The inner loop starts at column 1, so column 0 is only handled by the first_col_zero flag. Missing this means the first column never gets zeroed even when it should.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

In-place marker storage

The pattern of using existing elements (here, the first row and column) as auxiliary storage instead of allocating extra space:

# Use matrix[r][0] to mark "row r needs zeroing"
# Use matrix[0][c] to mark "column c needs zeroing"
for r in range(m):
    for c in range(1, n):
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0

This concept of borrowing input space for bookkeeping appears in many O(1)-space problems: marking visited indices in an array by negating values, using the array itself as a hash map in "first missing positive," and cycle sort variants. The common thread is the same: do not allocate new memory when the input has unused capacity you can repurpose.

Two-pass scan-then-apply

Separating the "gather information" pass from the "apply changes" pass is a fundamental pattern for in-place modifications:

# Pass 1: scan and record what needs to change
for r in range(m):
    for c in range(n):
        if condition(matrix[r][c]):
            record_change(r, c)

# Pass 2: apply all recorded changes
for r in range(m):
    for c in range(n):
        if should_change(r, c):
            matrix[r][c] = new_value

This two-pass approach prevents the cascading-modification bug where changes in the current pass interfere with decisions that have not been made yet. You will use it in Game of Life (LeetCode 289), image processing problems, and any scenario where reading and writing the same structure simultaneously would cause corruption.

When to reach for this pattern

Look for these signals:

• The problem says "modify in place" and "O(1) extra space"
• You need to propagate information across rows and columns of a matrix
• The matrix has unused capacity in its borders or specific positions that can serve as flags
• You would naturally use a set or array to track which rows/columns/indices need updating, but the space constraint forbids it

Whenever you see these, ask yourself: "Can I store my flags inside the input itself?" If the answer is yes, you probably want the in-place marker pattern.

From understanding to recall

You have walked through three approaches and understand why the O(1) solution works. But there are enough moving parts in the optimal version (the separate boolean, the backward iteration, the specific order of the four steps) that it is easy to fumble under pressure.

The fix is spaced repetition. You practice writing the marker-based solution from scratch: the scan loop that marks the first row and column, the backward zeroing loop, and the separate cleanup for the first row and first column. Do it today, again in two days, again in five. After a few reps, the order of operations is automatic. You see "set matrix zeroes" and the four-step structure just flows out.

The in-place marker pattern and the two-pass scan-then-apply pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the details stick.

Related posts

• Spiral Matrix - Another classic matrix traversal problem where careful boundary management is the key to a clean solution
• Rotate Array - In-place transformation using a clever trick (triple reversal) that avoids extra allocation, the same "borrow the input" mindset

CodeBricks breaks Set Matrix Zeroes into its in-place marker and two-pass scan building blocks, then drills them independently with spaced repetition. You type the marking loop, the backward zeroing loop, and the first-row/first-column cleanup from scratch until the pattern is automatic. When an in-place matrix problem shows up in your interview, you do not think about it. You just write it.