01 Matrix

Find the Duplicate Number

Flatten Binary Tree to Linked List

Return a matrix where each cell stores the Manhattan distance to the nearest zero in the input binary grid.

You are given an `m x n` binary matrix `mat` containing only `0`s and `1`s. Return a matrix of the same size where each cell stores the distance to the **nearest** `0`, using 4-directional moves (up, down, left, right).

**Input / output**
- Input: `mat: int[][]`
- Output: `int[][]` (distance from each cell to its nearest `0`)

**Examples**
1. `mat = [[0,0,0],[0,1,0],[0,0,0]]` returns `[[0,0,0],[0,1,0],[0,0,0]]` because every `0` stays at distance `0` and the center `1` is one step from a zero.
2. `mat = [[0,0,0],[0,1,0],[1,1,1]]` returns `[[0,0,0],[0,1,0],[1,2,1]]`; the bottom-middle cell is two moves away from its nearest zero.
3. `mat = [[0]]` returns `[[0]]`.

**Constraints**
- `1 <= m, n <= 10^4`
- `1 <= m * n <= 10^4`
- `mat[i][j]` is `0` or `1`
- There is at least one `0` in `mat`

**Follow-up**
How would the algorithm change if diagonal moves were allowed, or if you needed to answer many nearest-zero queries against the same static matrix?

- Treat every cell as a graph node with up to four neighbors.
- Running a separate shortest-path search from every `1` works, but repeats almost the same exploration many times.
- The key insight is to reverse the perspective: start BFS from **all zero cells at once**, so the first time you reach a cell is automatically its nearest-zero distance.

Start with the right graph view

- For every cell containing `1`, launch a BFS until you touch a `0`.
- That finds the correct nearest distance for that starting cell, because BFS explores in increasing path length order.
- But doing this independently for many cells can degrade to `O((m*n)^2)` time in the worst case.

Naive brute force: BFS from each 1-cell

- Instead of asking every `1` where its closest `0` is, let every `0` spread outward simultaneously.
- Put all zero cells into the queue with distance `0` before the BFS starts.
- Then each unvisited neighbor gets distance `current + 1`; because BFS expands by layers, the first assigned distance is the minimum one.

Improve it with multi-source BFS

- Initialize a distance matrix with `-1` to mean unvisited.
- Seed the queue with every zero cell and mark those distances as `0`.
- Pop cells in BFS order and assign each unseen neighbor its distance exactly once.

Optimal solution: one BFS from all zeros

Start with every zero already in the queue:

| BFS layer | Newly confirmed cells | Distance matrix state |
|---|---|---|
| initial | all zeros: `(0,0)`, `(0,1)`, `(0,2)`, `(1,0)`, `(1,2)` | `[[0,0,0],[0,-1,0],[-1,-1,-1]]` |
| distance 1 | `(1,1)`, `(2,0)`, `(2,2)` | `[[0,0,0],[0,1,0],[1,-1,1]]` |
| distance 2 | `(2,1)` | `[[0,0,0],[0,1,0],[1,2,1]]` |

The BFS layers stop there, and the final matrix is `[[0,0,0],[0,1,0],[1,2,1]]`.

Dry run on `[[0,0,0],[0,1,0],[1,1,1]]`

- Running a separate BFS from each `1` in the final solution, which is correct but too slow compared with multi-source BFS.
- Forgetting to enqueue **all** zero cells initially, which breaks the nearest-distance guarantee.
- Not marking neighbors as visited when enqueuing them, causing duplicate work or overwritten distances.
- Mixing up the four direction deltas or stepping diagonally by accident.

Common mistakes

- A matrix that is already all zeros should be returned unchanged.
- A `1x1` matrix containing `0` returns `[[0]]`.
- Single-row and single-column matrices still work because BFS only uses valid neighbors.
- Multiple zeros on different edges should all contribute as simultaneous BFS sources.

Edge cases to test mentally

Seed the queue with every zero and run one multi-source BFS over the grid. Each cell is enqueued and processed at most once, so the time complexity is `O(m*n)` and the extra space is `O(m*n)` for the queue plus distance/visited storage.