Set Matrix Zeroes

Table of Contents +

Set Matrix Zeroes looks easy at first. You find a zero. You set its row and column to zero. But there is a trap. If you change cells while you scan, you create new zeros. Then those fake zeros spread and wipe out cells that should stay. The interviewer wants to see if you can avoid that trap. And then they want to see you do it without extra memory.

🎯 The Problem

You get a grid of numbers and you must clear rows and columns. Here are the rules.

A grid like this is called a matrix. Rows go across, columns go down.
If any cell holds a 0, set its whole row to 0.
Set its whole column to 0 too.
Do this for every original zero. Then return the changed matrix.
The trap: do not let a fresh zero trigger more clearing.

Look at this small matrix. The cell at row 0, column 2 is a zero. So row 0 and column 2 both become all zeros.

Input:
1 1 0
1 1 1
1 1 1

Output:
0 0 0
1 1 0
1 1 0

Explanation: the zero at row 0 col 2 clears row 0 and column 2.

Here is a picture of how that one zero pushes its effect across its row and down its column.

🐢 Approach 1: Tag Cells With a Special Value (Brute Force)

The idea in one line: scan once, and tag each cell that must clear with a value that is not a real zero.

The idea:

Scan the matrix. When you find a zero, tag its whole row and column.
Use a tag like -1 or None, not a real 0.
A second pass turns every tag into a 0.

Why it is weak:

It breaks if the matrix already holds your tag value.
It is fragile. It only works when you know the data never uses that tag.
This is a weak answer. Mention it, then move on.

Here is the marker-value code:

def set_zeroes(matrix):
    marker = None
    rows, cols = len(matrix), len(matrix[0])

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                for x in range(cols):
                    if matrix[r][x] != 0:
                        matrix[r][x] = marker
                for x in range(rows):
                    if matrix[x][c] != 0:
                        matrix[x][c] = marker

    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] is marker:
                matrix[r][c] = 0

⚡ Approach 2: Two Marker Sets (Better)

The idea in one line: remember which rows and columns must clear in two sets, then clear in a second pass.

The idea:

First pass: just look. Change nothing.
Each zero adds its row number to one set and its column number to another set.
A set holds each value once.

How it works:

Now you have a list of rows to clear and columns to clear.
Second pass: walk the matrix again.
If a cell sits in a marked row or marked column, set it to 0.

Why it is weak:

It stores up to one entry per row and one per column.
The extra space is O(m + n), with m rows and n columns.
We can store those marks inside the matrix instead.

Here is the two-set code:

def set_zeroes(matrix):
    zero_rows = set()
    zero_cols = set()

    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            if matrix[r][c] == 0:
                zero_rows.add(r)
                zero_cols.add(c)

    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            if r in zero_rows or c in zero_cols:
                matrix[r][c] = 0

🚀 Approach 3: First Row and Column as Markers (Best)

The idea in one line: reuse the first row and first column of the matrix itself as the two marker lists.

The idea:

If cell (i, j) is zero, write 0 into matrix[i][0] and matrix[0][j].
The first cell of that row remembers “this row needs clearing”.
The first cell of that column remembers “this column needs clearing”.

The overlap to handle:

The first row and first column share the corner cell matrix[0][0].
One cell cannot mark both.
So matrix[0][0] marks the first row, and a separate flag firstColZero marks the first column.

How it works:

First, record whether the first row and first column already hold a zero, in two flags.
Then use the inner cells to write marks on row 0 and column 0.
Then clear the inner cells based on those marks.
Then clear the first row and first column last, using the flags.

Steps to Solve

Make a flag firstRowZero true if the first row has any zero.
Make a flag firstColZero true if the first column has any zero.
Walk every inner cell (skip row 0 and column 0). If it is 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
Walk every inner cell again. If its row marker matrix[i][0] is 0 or its column marker matrix[0][j] is 0, set the cell to 0.
If firstRowZero is true, set the whole first row to 0.
If firstColZero is true, set the whole first column to 0.

Here is a dry run of the optimal flow on the example.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses two flags for the first row and first column, then the matrix itself for the rest.

def set_zeroes(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))   # row 0 has a zero
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))   # col 0 has a zero

    for i in range(1, rows):              # mark inner zeros on row 0 and col 0
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    for i in range(1, rows):              # clear inner cells using markers
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    if first_row_zero:                    # clear first row last
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_zero:                    # clear first column last
        for i in range(rows):
            matrix[i][0] = 0


matrix = [[1, 1, 0], [1, 1, 1], [1, 1, 1]]
set_zeroes(matrix)
for row in matrix:
    print(" ".join(str(v) for v in row))

The output of the above code will be:

0 0 0
1 1 0
1 1 0

Let us walk through the Python version line by line, because the order of steps is everything here.

first_row_zero = any(matrix[0][j] == 0 for j in range(cols)) checks the top row before we touch it. We must remember this now. Later we will write zeros into row 0 as markers. So we cannot trust row 0 at the end. This flag saves the truth early.

first_col_zero = any(matrix[i][0] == 0 for i in range(rows)) does the same for the left column. Same reason. We are about to use column 0 as a notebook, so we record its real state first.

The first double loop starts at range(1, rows) and range(1, cols). So it skips row 0 and column 0. That is on purpose. Those border cells are our markers, not data we want to read as data yet. When an inner cell is 0, we write 0 into matrix[i][0] and matrix[0][j]. That is the note: “row i needs clearing” and “column j needs clearing.”

The second double loop also skips the border. It reads the markers. If matrix[i][0] is 0 or matrix[0][j] is 0, the cell gets cleared. We do this only for inner cells, so the markers stay safe while we read them.

The last two if blocks clear the border itself, using the flags we saved at the very start. We do the border last on purpose. If we cleared it earlier, we would erase our own notes.

⏱️ Time and Space Complexity

Every approach reads each cell a constant number of times. So the time is always O(m × n), where m is rows and n is columns. The difference is memory. The marker-sets version stores rows and columns, so it costs O(m + n) space. The optimal version reuses the matrix, so it costs only O(1) extra space.

Approach	Time Complexity	Space Complexity
Tag cells with a special value	O(m × n)	O(1)
Two marker sets	O(m × n)	O(m + n)
First row and column markers	O(m × n)	O(1)

Tip

The classic mistake is writing zeros while you scan. That spreads fake zeros and ruins the answer. Always mark first in a separate pass, then clear in a second pass.

🧩 Key Takeaways

✅ Never write a real zero during the scan. It creates new zeros and corrupts the result.
✅ The safe idea is to mark rows and columns first, then clear in a second pass.
✅ The optimal trick reuses the first row and first column as the marker lists.
✅ The corner cell clashes, so use one extra flag for the first column.
✅ Clear the first row and first column last, after every inner cell is done.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Spiral Matrix
Rotate Image

Previous Valid Parenthesis String Next Spiral Matrix

Set Matrix Zeroes

Follow Us

Follow Us