Multi-Source BFS Explained: Rotting Oranges and Nearest Exits

Some grid problems ask for a distance from many starting points at once: how long until every orange rots, how far each room is from the nearest gate, how far each land cell is from water. The tempting solution runs one breadth-first search per source. The right one runs a single search that starts from all of them together, and the change is one line: what goes into the queue before the loop starts.

The problem it solves

You have a grid and a set of source cells. For every other cell, find the distance to the nearest source, moving up, down, left or right, possibly around walls. The classic interview form is rotting oranges: each minute, every rotten orange rots its fresh neighbours; return the minutes until nothing is fresh, or -1 if some orange can never be reached.

With S sources on a grid of V cells, one BFS per source costs O(S × V), and taking the minimum per cell adds bookkeeping. When most cells can be sources, that is quadratic in the grid size.

The intuition

Plain BFS explores in rings: everything at distance 1, then everything at distance 2, and so on. The first time it reaches a cell is along a shortest path.

Now put every source into the queue at distance 0 before the first step. The queue still holds cells in order of distance, so the search still expands in rings, except now the rings grow around all the sources at once, like ripples from several stones dropped together. When two ripples meet, the cell is claimed by whichever arrived first, and that is exactly the nearest source. There is nothing to compare and nothing to revisit: a cell is labelled once, the first time any wave reaches it.

A useful mental model is one invisible super-source connected to every real source by an edge of length zero. Multi-source BFS is ordinary BFS from that super-source.

Watch it run

The animation uses a 3 by 3 floor with two exits, at (0, 0) and (1, 2). Both go into the queue at distance 0 before anything moves. Tile (0, 0) hands its neighbours 1, then tile (1, 2) hands its three unvisited neighbours 1. Tile (1, 0) hands (2, 0) a 2, and tile (2, 2) hands (2, 1) a 2. Every tile now holds its walk to the nearest exit, the worst is 2, and no tile was touched twice.

The code

One function for "distance to the nearest source", with an optional wall test. The lesson's floor comes out as the animation's final frame:

from collections import deque

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def nearest_source(grid, is_source, is_wall=lambda v: False):
    """Distance from every cell to its nearest source; -1 if none can reach it."""
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if is_source(grid[r][c]):
                dist[r][c] = 0                 # every source starts in the queue
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1
                    and not is_wall(grid[nr][nc])):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

floor = [["exit", ".", "."],
         [".", ".", "exit"],
         [".", ".", "."]]
for row in nearest_source(floor, lambda v: v == "exit"):
    print(row)
# [0, 1, 1]
# [1, 1, 0]
# [2, 2, 1]

Rotting oranges is the same function with rotten oranges as sources and empty cells as walls. The answer is the largest distance among fresh oranges, or -1 if one was never reached:

def oranges_rotting(grid):
    """0 empty, 1 fresh, 2 rotten. Minutes until nothing is fresh, or -1."""
    dist = nearest_source(grid, lambda v: v == 2, lambda v: v == 0)
    minutes = 0
    for r, row in enumerate(grid):
        for c, v in enumerate(row):
            if v == 1:
                if dist[r][c] == -1:
                    return -1                  # a fresh orange no rot can reach
                minutes = max(minutes, dist[r][c])
    return minutes

print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))   # 4
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))   # -1
print(oranges_rotting([[0, 2]]))                            # 0

The slow way as a reference: one BFS per source, then the minimum per cell. Both agree on 500 random grids with walls:

import random

def one_source(grid, sr, sc):
    rows, cols = len(grid), len(grid[0])
    d = [[-1] * cols for _ in range(rows)]
    d[sr][sc] = 0
    q = deque([(sr, sc)])
    while q:
        r, c = q.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and d[nr][nc] == -1 and grid[nr][nc] != 0:
                d[nr][nc] = d[r][c] + 1
                q.append((nr, nc))
    return d

def brute_nearest(grid):
    """One BFS per source, then the minimum per cell: the slow way."""
    rows, cols = len(grid), len(grid[0])
    best = [[-1] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                d = one_source(grid, r, c)
                for i in range(rows):
                    for j in range(cols):
                        if d[i][j] != -1 and (best[i][j] == -1 or d[i][j] < best[i][j]):
                            best[i][j] = d[i][j]
    return best

random.seed(16)
ok = True
for _ in range(500):
    rows, cols = random.randint(1, 6), random.randint(1, 6)
    g = [[random.choice([0, 1, 1, 1, 2]) for _ in range(cols)] for _ in range(rows)]
    ok &= nearest_source(g, lambda v: v == 2, lambda v: v == 0) == brute_nearest(g)
print(ok)                                      # True

The complexity

• One BFS per source: O(S × (V + E)) time. On a grid E is at most 4V, so that is O(S × V).
• Multi-source BFS: every cell enters the queue at most once and checks four neighbours, so O(V + E), which is O(rows × cols) on a grid, however many sources there are. The dist grid and the queue are O(V) space.

Where it goes wrong

• Marking visited on pop instead of push. If a cell is labelled only when it leaves the queue, two neighbours can both enqueue it and the queue fills with duplicates. Label it the moment it is pushed.
• Seeding the sources one at a time. Running the loop after each source is added is the slow version in disguise.
• Counting minutes with an off-by-one. A level-by-level loop that increments a counter per level often returns one too many, because the last level spreads to nobody. Reading the largest distance avoids that.
• Forgetting the unreachable case. A fresh orange walled off by empty cells keeps -1, and the answer must be -1, not the largest distance found.

When it shows up in interviews

It shows up as rotting oranges, walls and gates, the 0-1 matrix ("distance of each cell to the nearest 0"), and "as far from land as possible". All four are the same function with different sources and walls, and recognising that is what is being tested. The real-world versions are the same shape: the walking distance from every desk to the nearest fire exit, or the delivery time from the nearest warehouse to every district on a map.

How to say it in an interview

"I want each cell's distance to its nearest source, so instead of a BFS per source I put every source in the queue at distance 0 and run one BFS. The queue still processes cells in order of distance, so the first wave to reach a cell comes from its nearest source, and I label it once when I push it. That is O(rows × cols) time and space regardless of the number of sources. For rotting oranges the answer is the largest distance to a fresh orange, or -1 if one stays unlabelled."

Single-source BFS and why it finds shortest paths is in BFS explained, and the grid version of a connected region search is in number of islands.