# 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

| Item | Meaning |
|---|---|
| Input | A 2D integer matrix |
| Output | No return value |
| Mutation | Modify `matrix` in place |
| Rule | If `matrix[row][col] == 0`, set all cells in that row and column to `0` |

Function shape:

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

## Examples

For:

```python
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:

```python
[
    [1, 0, 1],
    [0, 0, 0],
    [1, 0, 1],
]
```

For:

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

There are zeroes at:

```text
row 0, col 0
row 0, col 3
```

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

```python
[
    [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:

```python
rows = set()
cols = set()
```

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

Second pass:

```python
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:

```python
matrix[row][0] = 0
matrix[0][col] = 0
```

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

```python
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:

```python
first_row_zero
first_col_zero
```

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

## Algorithm

Let:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | The matrix is scanned a constant number of times |
| Space | `O(1)` | Only two boolean variables are used |

## Implementation

```python
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:

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

Then record whether the first row originally has a zero:

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

And whether the first column originally has a zero:

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

Next, scan the inner matrix and write markers:

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

After markers are ready, apply them:

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

Finally, handle the first row and first column:

```python
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

```python
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()
```

| Test | Why |
|---|---|
| Center zero | Basic row and column zeroing |
| First row zeroes | Checks first row and first column handling |
| `[[1]]` | Single non-zero cell |
| `[[0]]` | Single zero cell |
| Single row | Entire row becomes zero |
| Single column | Entire column becomes zero |
| No zeroes | Matrix should stay unchanged |