73. Set Matrix Zeroes

Reformulated question¶

Given a matrix, if any cell is 0, make its whole row and whole column 0, modifying the same matrix in place.

Example:

[[1,1,1],
 [1,0,1],
 [1,1,1]]
-> [[1,0,1],
    [0,0,0],
    [1,0,1]]

Key trick¶

Use the first row and first column as marker arrays.

When matrix[r][c] == 0, mark:
- matrix[r][0] = 0
- matrix[0][c] = 0
Since matrix[0][0] cannot represent both "zero first row" and "zero first column", keep two separate booleans.

This gives \(O(1)\) extra space.

Trap¶

Common mistakes:

Zeroing cells immediately while scanning, which creates fake zeroes and spreads too much.
Forgetting that the first row and first column are reused as markers.
Using only matrix[0][0] for both first row and first column.
Zeroing first row/column too early, destroying marker information.
Missing 1 x n or m x 1 edge cases.

Why this question is interesting¶

It looks like simple simulation, but the real test is whether you can reuse the matrix itself as storage without corrupting future decisions.

Solve the problem with idiomatic python¶

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        rows, cols = len(matrix), len(matrix[0])

        # First row / col need separate flags because matrix[0][0]
        # cannot represent both states at once.
        first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
        first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

        # Use first row and first column as markers.
        for r in range(1, rows):
            for c in range(1, cols):
                if matrix[r][c] == 0:
                    matrix[r][0] = 0
                    matrix[0][c] = 0

        # Zero rows based on row markers.
        for r in range(1, rows):
            if matrix[r][0] == 0:
                for c in range(1, cols):
                    matrix[r][c] = 0

        # Zero columns based on column markers.
        for c in range(1, cols):
            if matrix[0][c] == 0:
                for r in range(1, rows):
                    matrix[r][c] = 0

        # Apply saved state for first row / col last.
        if first_row_zero:
            for c in range(cols):
                matrix[0][c] = 0

        if first_col_zero:
            for r in range(rows):
                matrix[r][0] = 0

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("matrix", "expected"),
    [
        (
            [[1, 1, 1], [1, 0, 1], [1, 1, 1]],
            [[1, 0, 1], [0, 0, 0], [1, 0, 1]],
        ),
        (
            [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]],
            [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]],
        ),
        (
            [[1, 2, 3]],
            [[1, 2, 3]],
        ),
        (
            [[1], [0], [3]],
            [[0], [0], [0]],
        ),
        (
            [[0]],
            [[0]],
        ),
        (
            [[1, 0, 3, 4]],
            [[0, 0, 0, 0]],
        ),
        (
            [[1], [2], [0], [4]],
            [[0], [0], [0], [0]],
        ),
        (
            [[1, 2], [3, 4]],
            [[1, 2], [3, 4]],
        ),
        (
            [[1, 2, 0], [4, 5, 6], [0, 8, 9]],
            [[0, 0, 0], [0, 5, 0], [0, 0, 0]],
        ),
    ],
)
def test_setZeroes(matrix, expected):
    Solution().setZeroes(matrix)
    assert matrix == expected

Comment my solution¶

Your solution is correct and uses the right idea: first row and first column as markers with two extra booleans.

Small comments:

Good:
- Correct \(O(mn)\) time and \(O(1)\) extra space.
- Correctly delays zeroing the first row and first column until the end.
- Correctly updates remove_first_row and remove_first_col during the scan.
Slight improvement:
- Initializing both flags from matrix[0][0] works, but is less clear than explicitly scanning first row and first column.
- The comments have a small typo and could better describe that the first pass writes markers for all zeroes.
- In the final first-row/first-col zeroing, you skip index 0; it still works because if either flag is true then matrix[0][0] is already 0, but zeroing the full row/col is a bit cleaner.

## Solution
class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m = len(matrix)
        n = len(matrix[0])

        # we must check this before the first scan that could modify that value
        remove_first_row = matrix[0][0] == 0
        remove_first_col = matrix[0][0] == 0

        # first scan: find 0 cells and set cell on first colunm
        # and first row to 0
        for row in range(m):
            for col in range(n):
                if matrix[row][col] == 0:
                    if row == 0:
                        remove_first_row = True
                    if col == 0:
                        remove_first_col = True
                    matrix[0][col] = 0
                    matrix[row][0] = 0

        for row in range(1, m):
            if matrix[row][0] == 0:
                for col in range(1, n):
                    matrix[row][col] = 0

        for col in range(1, n):
            if matrix[0][col] == 0:
                for row in range(1, m):
                    matrix[row][col] = 0

        if remove_first_col:
            for row in range(1, m):
                    matrix[row][0] = 0
        if remove_first_row:
            for col in range(1, n):
                    matrix[0][col] = 0

A slightly cleaner version of your style:

class Solution:
    def setZeroes(self, matrix: list[list[int]]) -> None:
        m, n = len(matrix), len(matrix[0])

        remove_first_row = any(matrix[0][col] == 0 for col in range(n))
        remove_first_col = any(matrix[row][0] == 0 for row in range(m))

        for row in range(1, m):
            for col in range(1, n):
                if matrix[row][col] == 0:
                    matrix[row][0] = 0
                    matrix[0][col] = 0

        for row in range(1, m):
            if matrix[row][0] == 0:
                for col in range(1, n):
                    matrix[row][col] = 0

        for col in range(1, n):
            if matrix[0][col] == 0:
                for row in range(1, m):
                    matrix[row][col] = 0

        if remove_first_row:
            for col in range(n):
                matrix[0][col] = 0

        if remove_first_col:
            for row in range(m):
                matrix[row][0] = 0