LeetCode 73: Set Matrix Zeroes

Problem Restatement

We are given an m x n integer matrix.

If any cell contains 0, we must set that cell’s entire row and entire column to 0.

The update must be done in place.

The official problem statement requires modifying the given matrix directly, rather than returning a new matrix. It also asks whether we can solve it using constant extra space.

Input and Output

Function shape:

def setZeroes(matrix: list[list[int]]) -> None:
    ...

Examples

For:

matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
]

The zero is at row 1, column 1.

So we set row 1 and column 1 to zero:

[
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1],
]

For:

matrix = [
    [0, 1, 2, 0],
    [3, 4, 5, 2],
    [1, 3, 1, 5],
]

There are zeroes at:

row 0, col 0
row 0, col 3

So row 0, column 0, and column 3 must become zero:

[
    [0, 0, 0, 0],
    [0, 4, 5, 0],
    [0, 3, 1, 0],
]

First Thought: Use Extra Row and Column Sets

A simple solution is to remember which rows and columns should become zero.

First pass:

rows = set()
cols = set()

Whenever we see matrix[row][col] == 0, add row to rows and col to cols.

Second pass:

if row in rows or col in cols:
    matrix[row][col] = 0

This works, but it uses extra space.

The problem asks for an in-place solution. We can do better by using the matrix itself as the marker storage.

Key Insight

We need to remember which rows and columns must become zero.

Instead of creating separate arrays, use:

1. The first cell of each row as that row’s marker.
2. The first cell of each column as that column’s marker.

For a zero at (row, col), mark:

matrix[row][0] = 0
matrix[0][col] = 0

Then later, when processing cell (row, col), set it to zero if:

matrix[row][0] == 0 or matrix[0][col] == 0

The only complication is that the first row and first column are also real matrix data.

So we need two booleans:

first_row_zero
first_col_zero

These remember whether the first row or first column originally contained a zero.

Algorithm

Let:

m = len(matrix)
n = len(matrix[0])

First, check whether the first row has a zero.

Then check whether the first column has a zero.

Next, scan the inner matrix from row 1 to m - 1 and column 1 to n - 1.

When a zero is found at (row, col), mark:

matrix[row][0] = 0
matrix[0][col] = 0

Then scan the inner matrix again.

For every cell (row, col), if its row marker or column marker is zero, set the cell to zero.

Finally:

1. If first_row_zero is true, zero out the first row.
2. If first_col_zero is true, zero out the first column.

Correctness

The first row and first column markers record exactly which inner rows and columns must become zero. Whenever an original inner cell is zero, the algorithm marks its row and column by writing zero into matrix[row][0] and matrix[0][col].

During the second inner scan, a cell becomes zero exactly when its row marker or column marker is zero. That means the cell is in a row or column that originally contained a zero, so setting it to zero is required.

The first row and first column need separate handling because they are used as marker storage. The booleans first_row_zero and first_col_zero preserve whether they originally contained zeroes before marker writes could change them.

After the inner cells are processed, the algorithm zeroes the first row and first column only when their original state requires it. Therefore every required row and column becomes zero, and no unrelated cell is changed.

Complexity

Implementation

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

        first_row_zero = False
        first_col_zero = False

        for col in range(n):
            if matrix[0][col] == 0:
                first_row_zero = True
                break

        for row in range(m):
            if matrix[row][0] == 0:
                first_col_zero = True
                break

        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):
            for col in range(1, n):
                if matrix[row][0] == 0 or matrix[0][col] == 0:
                    matrix[row][col] = 0

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

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

Code Explanation

We first read the matrix dimensions:

m = len(matrix)
n = len(matrix[0])

Then record whether the first row originally has a zero:

for col in range(n):
    if matrix[0][col] == 0:
        first_row_zero = True
        break

And whether the first column originally has a zero:

for row in range(m):
    if matrix[row][0] == 0:
        first_col_zero = True
        break

Next, scan the inner matrix and write markers:

if matrix[row][col] == 0:
    matrix[row][0] = 0
    matrix[0][col] = 0

After markers are ready, apply them:

if matrix[row][0] == 0 or matrix[0][col] == 0:
    matrix[row][col] = 0

Finally, handle the first row and first column:

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

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

This order matters. The first row and first column should be zeroed after the inner matrix has already used them as markers.

Testing

def run_tests():
    s = Solution()

    matrix = [
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ]
    s.setZeroes(matrix)
    assert matrix == [
        [1, 0, 1],
        [0, 0, 0],
        [1, 0, 1],
    ]

    matrix = [
        [0, 1, 2, 0],
        [3, 4, 5, 2],
        [1, 3, 1, 5],
    ]
    s.setZeroes(matrix)
    assert matrix == [
        [0, 0, 0, 0],
        [0, 4, 5, 0],
        [0, 3, 1, 0],
    ]

    matrix = [[1]]
    s.setZeroes(matrix)
    assert matrix == [[1]]

    matrix = [[0]]
    s.setZeroes(matrix)
    assert matrix == [[0]]

    matrix = [[1, 0, 3]]
    s.setZeroes(matrix)
    assert matrix == [[0, 0, 0]]

    matrix = [
        [1],
        [0],
        [3],
    ]
    s.setZeroes(matrix)
    assert matrix == [
        [0],
        [0],
        [0],
    ]

    matrix = [
        [1, 2, 3],
        [4, 5, 6],
    ]
    s.setZeroes(matrix)
    assert matrix == [
        [1, 2, 3],
        [4, 5, 6],
    ]

    print("all tests passed")

run_tests()