“For every cell, how far is the nearest zero?” invites a BFS from each cell, which is $O((mn)^2)$ and hopeless. Reverse the question and it collapses:

Instead of searching from each cell to the nearest source, push every source into the queue at once and let one BFS expand outward from all of them simultaneously.

The first time any wave reaches a cell, it arrived from the nearest source — because BFS expands in non-decreasing distance order and all sources started at distance 0. One pass, $O(mn)$, no repeated work.

This is one of those patterns that feels like a trick the first time and obvious forever after.

What you’ll learn

• Why seeding many sources still yields correct shortest distances.
• The level loop that converts BFS layers into elapsed time or distance.
• The two ways to track visited cells — and the “distance array doubles as visited” idiom.
• How to detect unreachable cells, which is what most of these problems actually test.
• Three real LeetCode problems solved in the browser: 994, 542, 1162.

The cue

Template 1 — distance to the nearest source

The distance array doubles as the visited marker, which removes a whole category of bugs.

from collections import deque
 
 
def nearest_source_distance(grid, is_source):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]     # -1 means "not yet reached"
    queue = deque()
 
    for r in range(rows):                        # SEED every source at once
        for c in range(cols):
            if is_source(grid[r][c]):
                dist[r][c] = 0
                queue.append((r, c))
 
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1    # set distance = mark visited
                queue.append((nr, nc))
 
    return dist

from collections import deque
 
 
def nearest_source_distance(grid, is_source):
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]     # -1 means "not yet reached"
    queue = deque()
 
    for r in range(rows):                        # SEED every source at once
        for c in range(cols):
            if is_source(grid[r][c]):
                dist[r][c] = 0
                queue.append((r, c))
 
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1    # set distance = mark visited
                queue.append((nr, nc))
 
    return dist

Template 2 — elapsed time, via level loops

When the answer is “how many minutes/steps”, process the queue one level at a time, exactly as in Tree BFS.

steps = 0
while queue and still_work_remaining:
    steps += 1
    for _ in range(len(queue)):          # snapshot: exactly this level
        r, c = queue.popleft()
        # ... expand neighbours, appending to the same queue

steps = 0
while queue and still_work_remaining:
    steps += 1
    for _ in range(len(queue)):          # snapshot: exactly this level
        r, c = queue.popleft()
        # ... expand neighbours, appending to the same queue

The for _ in range(len(queue))for _ in range(len(queue)) snapshot is what separates one time step from the next. Without it every cell would be its own “minute”.

Detecting unreachable cells

This is what most of these problems really test. After the BFS finishes, any cell still holding the initial sentinel was never reached:

• 994 Rotting Oranges — a fresh orange remains: return -1-1.
• 542 01 Matrix — guaranteed at least one zero, so everything is reachable.
• 1162 As Far from Land as Possible — all-water or all-land: return -1-1.

Rather than rescanning the grid at the end, it is usually cleaner to keep a counter of the remaining work (freshfresh in LC 994) and decrement it as you convert cells. Then fresh == 0fresh == 0 is an $O(1)$ check instead of an $O(mn)$ sweep — and it also lets you stop the loop early.

The variant map

Practice — real LeetCode problems

LC 994 — Rotting Oranges · Medium

Problem. In a grid, 00 is empty, 11 is a fresh orange, 22 is rotten. Each minute, every fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1-1 if that is impossible.

Constraints. 1 <= m, n <= 101 <= m, n <= 10, cells are 00, 11 or 22.

Examples. [[2,1,1],[1,1,0],[0,1,1]][[2,1,1],[1,1,0],[0,1,1]] gives 44 · [[2,1,1],[0,1,1],[1,0,1]][[2,1,1],[0,1,1],[1,0,1]] gives -1-1 (the bottom-left 11 is isolated) · [[0,2]][[0,2]] gives 00

LC 542 — 01 Matrix · Medium

Problem. Given an m x nm x n binary matrix, return a matrix of the same shape where each entry is the distance to the nearest 00, measured in 4-directional steps.

Constraints. 1 <= m, n <= 10^41 <= m, n <= 10^4, m * n <= 10^4m * n <= 10^4, and there is at least one 00.

Examples. [[0,0,0],[0,1,0],[0,0,0]][[0,0,0],[0,1,0],[0,0,0]] gives itself unchanged · [[0,0,0],[0,1,0],[1,1,1]][[0,0,0],[0,1,0],[1,1,1]] gives [[0,0,0],[0,1,0],[1,2,1]][[0,0,0],[0,1,0],[1,2,1]]

LC 1162 — As Far from Land as Possible · Medium

Problem. Given an n x nn x n grid of 00 (water) and 11 (land), find the water cell whose distance to the nearest land cell is maximised, and return that distance (Manhattan / 4-directional). If no water or no land exists, return -1-1.

Constraints. 1 <= n <= 1001 <= n <= 100, cells are 00 or 11.

Examples. [[1,0,1],[0,0,0],[1,0,1]][[1,0,1],[0,0,0],[1,0,1]] gives 22 (the centre) · [[1,0,0],[0,0,0],[0,0,0]][[1,0,0],[0,0,0],[0,0,0]] gives 44 (the far corner) · [[0,0],[0,0]][[0,0],[0,0]] gives -1-1

LeetCode problem set

Interview follow-ups

Edge-case checklist

• No sources at all — LC 994 with only fresh oranges gives -1-1; LC 1162 with no land gives -1-1.
• No targets at all — LC 994 with no fresh oranges gives 00; LC 1162 with no water gives -1-1. Both degenerate cases need guards.
• Everything is a source — the queue starts full and no level ever expands.
• Unreachable cells — an isolated fresh orange behind empty cells; the reason for the counter check.
• 1×1 grid — every variant must survive it.
• Off-by-one in the level counter — initialise -1-1 when the source level counts as distance 0, and 00 when counting elapsed steps.
• One wasted final minute (LC 994) — while queue and freshwhile queue and fresh rather than while queuewhile queue.
• Duplicate enqueues — guaranteed if you mark on dequeue instead of enqueue.

Recap

• Seed the queue with every source and run one BFS. Correct because it is BFS from a virtual super-source, so the first visit to a cell is its shortest distance.
• Turns $O((mn)^2)$ into $O(mn)$. If you are about to loop “BFS per source”, invert it.
• Mark visited on enqueue, never on dequeue — with many sources, duplicate enqueues are otherwise guaranteed.
• A distance array initialised to -1-1 is both the answer and the visited set.
• For elapsed time, process one level per step with a len(queue)len(queue) snapshot.
• Track remaining work with a counter for $O(1)$ termination and unreachability checks.
• Requires uniform edge cost; weighted versions are Dijkstra (with all sources pushed at distance 0).

Next: Union-Find Problem Patterns — the other way to answer connectivity questions, and the one that handles edges arriving over time.