Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Set Matrix Zeroes
• Main tags: Array, Hash Table, Matrix

What the problem is really asking

The rule sounds simple:

if any cell contains 0, then every cell in that cell’s row and every cell in that cell’s column must become 0.

The catch is that the update must happen “at once.”

That means once the algorithm starts writing zeroes into the matrix, it cannot accidentally treat those newly written zeroes as if they were part of the original input. If it does, the zeroes spread too far and the answer becomes wrong.

So the real problem is not “how do we zero rows and columns?”

It is:

how do we remember which rows and columns need to be cleared, without letting intermediate writes corrupt the decision?

The easiest way to derive the solution

The most natural first idea is to separate detection from mutation.

During one pass, record:

• which rows contain at least one zero
• which columns contain at least one zero

Then during a second pass, set matrix[row][column] to 0 whenever that row or column was marked.

That solution is already good:

• Time: O(m * n)
• Extra space: O(m + n)

Once that is clear, the interview usually asks for the in-place follow-up.

At that point, the key observation is that the matrix already has storage we can reuse:

• the first cell of each row can mark whether that row should become zero
• the first cell of each column can mark whether that column should become zero

In other words, instead of storing markers in extra arrays, store them in:

• matrix[row][0]
• matrix[0][column]

That is the optimal trick.

The only subtlety

The first row and first column now have two jobs:

1. they are real data
2. they are the marker storage

So before using them as markers, the algorithm must separately remember:

• whether the first row originally contained a zero
• whether the first column originally contained a zero

Without that step, the algorithm would not know whether the first row or first column should be cleared at the end because of the original input, or because marker values were written there later.

That is why almost every clean solution has four phases:

1. inspect the first row
2. inspect the first column
3. use the interior of the matrix to write row/column markers into the first row and first column
4. zero the marked interior cells, then finish the first row and first column if needed

Best approaches

The row-set and column-set solution is often the best way to explain the idea first because it makes the logic obvious. It runs in O(m * n) time with O(m + n) extra space.

The optimal answer keeps the same O(m * n) runtime but reduces extra space to O(1) by reusing the first row and first column as marker storage. That is the version interviewers usually want for the follow-up and the version below implements.

Python solution

from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Modify the matrix in place so that every row and column containing
        an original zero becomes all zeroes.
        """
        if not matrix or not matrix[0]:
            return

        self._apply_zeroes_in_place(matrix)

    def _apply_zeroes_in_place(self, matrix: List[List[int]]) -> None:
        row_count = len(matrix)
        column_count = len(matrix[0])

        first_row_has_zero = self._row_contains_zero(
            matrix=matrix,
            row_index=0,
            column_count=column_count,
        )
        first_column_has_zero = self._column_contains_zero(
            matrix=matrix,
            column_index=0,
            row_count=row_count,
        )

        # Use the first row and first column as the in-place marker arrays.
        self._mark_rows_and_columns(
            matrix=matrix,
            row_count=row_count,
            column_count=column_count,
        )

        # Zero the interior based on the markers.
        self._zero_marked_interior(
            matrix=matrix,
            row_count=row_count,
            column_count=column_count,
        )

        if first_row_has_zero:
            self._zero_row(matrix=matrix, row_index=0, column_count=column_count)

        if first_column_has_zero:
            self._zero_column(matrix=matrix, column_index=0, row_count=row_count)

    @staticmethod
    def _row_contains_zero(
        matrix: List[List[int]],
        row_index: int,
        column_count: int,
    ) -> bool:
        for column_index in range(column_count):
            if matrix[row_index][column_index] == 0:
                return True
        return False

    @staticmethod
    def _column_contains_zero(
        matrix: List[List[int]],
        column_index: int,
        row_count: int,
    ) -> bool:
        for row_index in range(row_count):
            if matrix[row_index][column_index] == 0:
                return True
        return False

    @staticmethod
    def _mark_rows_and_columns(
        matrix: List[List[int]],
        row_count: int,
        column_count: int,
    ) -> None:
        for row_index in range(1, row_count):
            for column_index in range(1, column_count):
                if matrix[row_index][column_index] == 0:
                    matrix[row_index][0] = 0
                    matrix[0][column_index] = 0

    @staticmethod
    def _zero_marked_interior(
        matrix: List[List[int]],
        row_count: int,
        column_count: int,
    ) -> None:
        for row_index in range(1, row_count):
            row_should_be_zero = matrix[row_index][0] == 0
            for column_index in range(1, column_count):
                column_should_be_zero = matrix[0][column_index] == 0
                if row_should_be_zero or column_should_be_zero:
                    matrix[row_index][column_index] = 0

    @staticmethod
    def _zero_row(
        matrix: List[List[int]],
        row_index: int,
        column_count: int,
    ) -> None:
        for column_index in range(column_count):
            matrix[row_index][column_index] = 0

    @staticmethod
    def _zero_column(
        matrix: List[List[int]],
        column_index: int,
        row_count: int,
    ) -> None:
        for row_index in range(row_count):
            matrix[row_index][column_index] = 0

The central idea is that the algorithm treats the first row and first column as a tiny control panel. Each marker says, “this row must be zeroed later” or “this column must be zeroed later.” The separate first_row_has_zero and first_column_has_zero flags protect the original meaning of those two special regions.

Why this works

Suppose an interior cell matrix[row][column] is 0 in the original matrix.

During the marking pass, the algorithm writes:

• matrix[row][0] = 0
• matrix[0][column] = 0

That permanently records that the entire row and the entire column must eventually become zero.

Later, when the algorithm scans the interior again, it zeros a cell if either of these is true:

• its row marker is zero
• its column marker is zero

That matches the exact problem rule.

The only place where marker storage could interfere with real data is the first row and first column themselves. That is why the algorithm handles them last, using the saved booleans from the original matrix.

So every required row and column is zeroed, and no extra row or column is zeroed by accident.

Interview follow-ups

What if the interviewer first wants the simplest correct solution?

Start with two auxiliary sets, or two boolean arrays, to track which rows and columns contain an original zero. The first pass fills those markers. The second pass zeroes any cell whose row or column is marked. This is often the easiest way to communicate the core idea because it cleanly separates “discover what must change” from “apply the changes.” It runs in O(m * n) time with O(m + n) extra space. Once that is accepted, the in-place solution is a natural optimization rather than a magic trick.

Why can’t the matrix be updated immediately when a zero is found?

Because a newly written zero is not part of the original input. If the algorithm writes zeroes too early and then keeps scanning, it may interpret those new zeroes as fresh triggers and incorrectly zero extra rows and columns. A simple counterexample is a matrix with one original zero in the middle. If the row is zeroed immediately, later cells in that row look like original zeroes even though they were created by the algorithm. The correct strategy is to separate detection from mutation, either with external storage or with in-place markers.

How would the approach change if modifying the input were forbidden?

Then the first-row and first-column marker trick is off the table because it relies on temporarily overwriting the matrix. The clean replacement is to keep explicit row and column markers in additional memory, or to build a fresh output matrix from a copy of the input. The time complexity stays O(m * n), but the space becomes O(m + n) for marker arrays or O(m * n) for a full copy. The tradeoff is straightforward: less mutation risk and easier reasoning, but more memory.

What if the matrix is very large but only a few cells are zero?

If the interview becomes more systems-oriented, sparsity can matter. The asymptotically optimal in-place algorithm still scans the full matrix because the output itself may require touching many cells. But if the task were changed to record the transformation lazily rather than materialize it immediately, a sparse representation of zero rows and zero columns could be useful. In the standard LeetCode problem, though, the answer must mutate the actual matrix, so an O(m * n) full scan remains the right baseline and the real optimization target is extra space, not runtime.