01 Matrix
01 Matrix: for a grid of 0s and 1s, return the distance from each cell to its nearest 0.
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10⁴
- 1 <= m * n <= 10⁴
- mat[i][j] is either 0 or 1.
- There is at least one 0 in mat.
Intuition
01 matrix asks, for every cell in a grid of zeros and ones, the distance to the nearest zero. The obvious plan is to BFS outward from each 1 until a 0 is found, but that repeats enormous amounts of work — each search re-explores territory its neighbours already covered — and costs O(cells²).
The fix is to reverse the direction of the search. Instead of asking each 1 to find a zero, let all the zeros spread outward simultaneously:
- Seed the queue with every zero cell at distance 0, then run a single multi-source BFS.
Because BFS visits cells in non-decreasing distance order from the combined source set, the first time any cell is reached, it is reached from its nearest zero. No comparison between competing sources is ever needed — the traversal order settles it.
That is the same technique as Rotting Oranges: many starting points, one traversal, layers as distance.
Two implementation details. Mark cells as unvisited with a sentinel — typically -1 or infinity — so the traversal can distinguish "not yet reached" from a genuine distance of zero. And set each cell's distance when it is enqueued, not when dequeued, so it cannot be enqueued twice from two different neighbours.
The result is one pass over the grid to seed, and one BFS that touches each cell exactly once.
Multi-source BFS from every zero simultaneously. Because all sources start at distance 0, the wave reaches each cell by its shortest route automatically — no per-cell comparison needed, and dist doubles as the visited marker.
Approach
Before reading on: price up what enumerating every case costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(R*C) time and O(R*C) space.
Reverse the search direction
Searching outward from each 1 repeats work across neighbouring cells at O(cells²). Spreading from the zeros instead means one traversal answers every cell at once.
Seed every zero at distance 0
Scan the grid once, pushing all zero cells into the queue with distance 0 and marking every 1 as unvisited. Seeding all sources together is what makes one BFS sufficient.
Use a sentinel for unvisited
Mark unreached cells with -1 or infinity, so the traversal can tell not yet reached apart from a real distance of zero. Reusing 0 for both is the standard bug here.
Set the distance at enqueue time
Assign a neighbour's distance as it enters the queue, not when it comes out. This prevents the same cell being enqueued twice from two different neighbours, which would waste work and could overwrite a correct value.
Trust first-touch as shortest
BFS reaches cells in non-decreasing distance order from the whole source set, so the first time a cell is touched it comes from its nearest zero. No comparison between sources is needed.
Recognise the shared pattern
This is the same multi-source BFS as Rotting Oranges — many starting points, one traversal, layers as distance. Naming the pattern makes both problems one technique rather than two.
Cost of the sweep
Each cell is enqueued and dequeued at most once, giving O(rows × cols) time and the same bound on space for the queue in the worst case.
Solution & live demo
Common pitfalls
Running BFS from each 1
for each cell with 1: bfs to nearest 0
for each cell with 0: q.append((r, c))
That's a separate search per cell — O((RC)²) in the worst case. Seeding every zero at distance 0 computes all answers in one pass over the grid.
Using a separate visited array
visited = [[False] * C for _ in range(R)]
dist[nr][nc] is None
None in the distance grid already means unvisited, so a second structure is redundant bookkeeping that can drift out of sync. The first write is also the visit mark.
Writing the distance when dequeuing
r, c = q.popleft() dist[r][c] = ...
dist[nr][nc] = dist[r][c] + 1 q.append((nr, nc))
A cell reachable from two sources gets enqueued twice before either is processed, so the second entry overwrites with a larger distance. Marking at enqueue time admits each cell exactly once, at its true minimum.
Edge cases
Every cell is a source with distance 0; nothing is enqueued.
It is reached in the very first layer, distance 1.
Either [[0]] (distance 0) since at least one 0 is guaranteed to exist.
Distances grow with BFS depth from the nearest border of 0s, still one pass.