01 Matrix Solution

Problem

Given a binary matrix where each cell is either 0 or 1, find the shortest distance from each cell to the nearest cell containing a 0. Distance is measured in 4-directional steps (up, down, left, right).

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation: The 1-cell in the center of the middle row is one step from a 0; the three bottom-row 1-cells are 1, 2, and 1 steps from the nearest zeros above them.

Counter-example: mat = [[1,1],[1,1]] would have no solution — the problem guarantees at least one 0-cell exists in the matrix.

Intuition

Every 0-cell already has a distance of 0. The challenge is propagating those known answers outward to all 1-cells without repeating work. The key insight is to reverse the search direction: instead of launching a separate BFS from each 1-cell toward the nearest 0, seed the queue with every 0-cell simultaneously and let a single BFS wave expand outward. The first time that wave reaches any 1-cell, that depth is the shortest distance to any 0 — guaranteed by how BFS explores in non-decreasing distance order.

Approach 1 — BFS per Cell

For each 1-cell, run a dedicated BFS that stops the moment it reaches any 0-cell. This is correct but redundant: neighboring 1-cells launch completely independent searches that traverse much of the same grid.

For each cell (r, c) with value 1, initialize a BFS queue containing just that cell.
Expand to the four neighbors, tracking visited cells to avoid loops.
The moment a 0-cell is dequeued, record its depth as distances[r][c] and stop — BFS guarantees this is the shortest path.
Cells with value 0 already have their answer (distance 0) from initialization.

1from collections import deque
2
3def updateMatrix(mat: list[list[int]]) -> list[list[int]]:
4    rows, cols = len(mat), len(mat[0])
5    distances = [[0] * cols for _ in range(rows)]
6    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
7
8    def nearest_zero_distance(start_r: int, start_c: int) -> int:
9        queue = deque([(start_r, start_c, 0)])
10        visited = {(start_r, start_c)}
11        while queue:
12            r, c, depth = queue.popleft()
13            if mat[r][c] == 0:
14                return depth  # BFS guarantees this is the shortest path to any 0
15            for dr, dc in directions:
16                nr, nc = r + dr, c + dc
17                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
18                    visited.add((nr, nc))
19                    queue.append((nr, nc, depth + 1))
20        return rows * cols  # unreachable when the matrix contains at least one 0
21
22    for r in range(rows):
23        for c in range(cols):
24            if mat[r][c] == 1:
25                distances[r][c] = nearest_zero_distance(r, c)
26    return distances

Time: O((m·n)²) — for each of up to m·n cells containing a 1, the BFS may visit all m·n cells in the worst case.
Space: O(m·n) — the visited set and queue for a single BFS run; only one runs at a time.

Approach 2 — Multi-Source BFS (Optimal)

Reverse the search: seed the BFS queue with every 0-cell simultaneously and expand outward. Since all sources propagate in parallel, each 1-cell is reached at the earliest possible wave depth — no cell's computation duplicates another's work.

Initialize distances to 0 for every 0-cell and to a large sentinel for every 1-cell.
Add every 0-cell to the queue as a starting node at depth 0.
For each dequeued cell, examine all four neighbors.
If a neighbor's stored distance is greater than current_distance + 1, update it and enqueue that neighbor.

1from collections import deque
2
3def updateMatrix(mat: list[list[int]]) -> list[list[int]]:
4    rows, cols = len(mat), len(mat[0])
5    distances = [[float('inf')] * cols for _ in range(rows)]
6    queue = deque()
7
8    for r in range(rows):
9        for c in range(cols):
10            if mat[r][c] == 0:
11                distances[r][c] = 0
12                queue.append((r, c))  # all 0-cells are BFS sources at depth 0
13
14    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
15    while queue:
16        r, c = queue.popleft()
17        for dr, dc in directions:
18            nr, nc = r + dr, c + dc
19            if (0 <= nr < rows and 0 <= nc < cols and
20                    distances[nr][nc] > distances[r][c] + 1):
21                distances[nr][nc] = distances[r][c] + 1  # first arrival is always shortest
22                queue.append((nr, nc))
23
24    return distances

Time: O(m·n) — each cell is enqueued and processed at most once across the entire BFS.
Space: O(m·n) — the queue holds at most all m·n cells.

Complexity Summary

Approach	Time	Space	When to use
BFS per Cell	O((m·n)²)	O(m·n)	Only when the grid is tiny and clarity beats performance
Multi-Source BFS	O(m·n)	O(m·n)	Default choice — same conceptual simplicity with far better performance

Common Mistakes

BFS from each 1-cell toward 0s instead of from all 0-cells outward — both directions produce a correct brute force, but only seeding from all 0-cells at once enables the single-pass optimal solution; searching from each 1-cell individually repeats work for every pair of adjacent 1-cells.
Seeding only one 0-cell into the initial queue — multi-source BFS requires every 0-cell to be in the queue from the start; adding them one at a time destroys the shared-wave property and degrades back toward O((m·n)²).
Using INT_MAX as the sentinel and adding 1 to it — INT_MAX + 1 overflows to INT_MIN in C++ (undefined behavior) and wraps to a large negative value in Java, making the > guard backwards and producing wildly wrong distances; use INT_MAX / 2 or rows * cols + 1 as the sentinel instead.
Skipping bounds checking before accessing a neighbor — edge and corner cells have fewer than four valid neighbors; accessing distances[nr][nc] without verifying nr and nc are in range causes an array index out of bounds crash.
Re-enqueuing cells without the distance guard — omitting the distances[nr][nc] > distances[r][c] + 1 check lets the same cell enter the queue many times; a later dequeue may overwrite a correct small distance with a larger value from a slower path.

01 Matrix — Solution