Multi-Source BFS

Rotting Oranges

You are given a grid where each cell is one of three values: 0 for empty, 1 for a fresh orange, and 2 for a rotten orange. Every minute, any fresh orange adjacent (up, down, left, right) to a rotten orange becomes rotten. How many minutes must pass until no fresh orange remains? If it is impossible for all oranges to rot, return -1.

This is LeetCode 994, and it is the classic introduction to multi-source BFS. The rotten oranges all start spreading simultaneously, not one after another. Minute 1 does not belong to any single rotten orange; all of them infect their neighbors at the same time. This simultaneous propagation from multiple starting points is what distinguishes multi-source BFS from the single-source variant.

Why This Is Different From Single-Source BFS

In ordinary BFS, you have one starting node. You enqueue it at distance 0, then explore its neighbors at distance 1, their neighbors at distance 2, and so on. The BFS wavefront expands outward from a single point.

Multi-source BFS has multiple starting nodes that all begin expanding at the same time. Think of dropping several stones into a pond simultaneously. Each stone creates ripples, and the ripples expand outward in parallel. Where two ripples meet, the water is already disturbed, so the second ripple has no additional effect. The result is that each point in the pond is reached by whichever stone was closest.

This is exactly what we want for Rotting Oranges: each fresh orange rots at the earliest possible time, determined by whichever rotten orange is closest to it.

The Key Trick: Enqueue All Sources at Distance 0

The implementation is surprisingly simple. Before BFS begins, scan the grid and enqueue every rotten orange with distance 0. Then run standard BFS from this pre-loaded queue. When you dequeue a cell at distance d and find a fresh neighbor, that neighbor becomes rotten at distance d + 1. Since all sources started at distance 0 in the same queue, the BFS naturally processes them in the correct order, level by level.

This works because BFS processes nodes in order of increasing distance. All the initial rotten oranges are at distance 0, so they are processed first. Their fresh neighbors become distance 1. Then all distance-1 cells are processed, and their fresh neighbors become distance 2. The wavefronts from different sources interleave perfectly in the queue.

The Virtual Super-Source Perspective

There is an elegant way to think about why this works. Imagine adding a virtual node, a "super-source," that is connected to every real source with an edge of cost 0. Running single-source BFS from this super-source would first visit the super-source at distance 0, then visit all real sources at distance 0 (since the edges cost 0), and then proceed with normal BFS. The distances from the super-source to any non-source cell would be exactly the minimum distance from any real source to that cell.

Multi-source BFS skips the virtual node and directly enqueues all real sources at distance 0. The effect is identical. You get the shortest distance from the nearest source to every reachable cell, computed in a single BFS pass.

Walking Through a Grid of Oranges

Consider this 3x3 grid where R is rotten, F is fresh, and E is empty:

R F F F F E E F R

The rotten oranges are at positions (0,0) and (2,2). We enqueue both at time 0.

Minute 0 queue: [(0,0), (2,2)].

Process (0,0) at time 0. Fresh neighbors: (0,1) and (1,0). Both become rotten at time 1. Process (2,2) at time 0. Fresh neighbor: (1,2) is out of bounds... wait, let us index carefully. Neighbors of (2,2) are (1,2) and (2,1). Cell (1,2) is empty, skip. Cell (2,1) is fresh, becomes rotten at time 1.

After minute 0: grid state has rotten at (0,0), (0,1), (1,0), (2,1), (2,2).

Minute 1 queue: [(0,1), (1,0), (2,1)].

Process (0,1) at time 1. Neighbor (0,2) is fresh, becomes rotten at time 2. Neighbor (1,1) is fresh, becomes rotten at time 2. Neighbor (0,0) is already rotten, skip. Process (1,0) at time 1. Neighbor (1,1) is already queued at time 2, skip (it is no longer fresh). Neighbor (0,0) already rotten. Process (2,1) at time 1. Neighbor (1,1) already handled. Neighbor (2,0) is empty.

After minute 1: grid has rotten at all previous plus (0,2), (1,1).

Minute 2 queue: [(0,2), (1,1)].

Process these. All their fresh neighbors are already rotten or empty. Queue becomes empty.

The last orange rotted at time 2, so the answer is 2. Notice how the two wavefronts from (0,0) and (2,2) met in the middle and each cell was claimed by whichever source was closer.

Code: Rotting Oranges

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh_count += 1

    if fresh_count == 0:
        return 0

    time_elapsed = 0
    while queue:
        r, c, t = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh_count -= 1
                queue.append((nr, nc, t + 1))
                time_elapsed = t + 1

    return time_elapsed if fresh_count == 0 else -1

We scan the grid once to enqueue all rotten oranges and count fresh ones. Each cell carries its timestamp. When a fresh orange is reached, we mark it rotten immediately (so it is not enqueued twice), decrement the fresh count, and record the time. At the end, if any fresh oranges remain, they were unreachable, so we return -1.

Marking the cell as rotten in the grid itself serves as our visited array. There is no need for a separate distance matrix because we only care about the final time, not the distance to every cell.

01 Matrix: Distance From Each 1 to the Nearest 0

LeetCode 542 gives you a binary matrix and asks you to find the distance from each cell to the nearest 0. This is multi-source BFS with every 0-cell as a source.

The idea: all 0-cells start at distance 0. BFS spreads outward. Each 1-cell gets assigned the distance of the first wavefront that reaches it, which is the distance to the nearest 0.

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == float('inf'):
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    return dist

This is the purest form of the multi-source BFS template. Initialize all sources at distance 0, set everything else to infinity, and let BFS fill in the rest. The dist[nr][nc] == float('inf') check ensures each cell is visited only once, by the closest source.

Walls and Gates

With LeetCode 286, you are given a grid with walls (-1), gates (0), and empty rooms (INF, represented as 2147483647). Fill each empty room with the distance to the nearest gate.

This is the same pattern. Gates are sources at distance 0. Walls are impassable. BFS from all gates simultaneously fills every reachable room with its shortest distance to any gate.

from collections import deque

def walls_and_gates(rooms):
    if not rooms:
        return
    rows, cols = len(rooms), len(rooms[0])
    INF = 2147483647
    queue = deque()

    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))

The grid itself stores distances, so we modify it in place. We only visit cells that are still INF (unvisited rooms). Walls are -1 and gates are 0, neither of which equals INF, so they are naturally skipped.

Why You Cannot BFS From Each Source Separately

A tempting but wrong approach is to loop over each source and run a separate BFS from it, updating distances as you go. This would work for correctness, but the time complexity is terrible.

If there are k sources and the grid has m rows and n columns, each individual BFS takes $O(m \cdot n)$. Running k of them takes $O(k \cdot m \cdot n)$. In the worst case, k could be close to $m \cdot n$ (imagine a grid that is mostly 0s), making this $O((m \cdot n)^2)$.

Multi-source BFS processes the entire grid in a single pass. Each cell is enqueued and dequeued at most once, regardless of how many sources exist. The total work is $O(m \cdot n)$, the same as a single BFS. The key is that once a cell has been reached by the closest source, it is marked as visited and never processed again. Later, farther sources cannot overwrite it.

This is the fundamental advantage of the multi-source technique: you get the effect of running BFS from every source, but you only pay the cost of running it once.

Complexity Analysis

Time complexity is $O(m \cdot n)$ for a grid with m rows and n columns. The initial scan to find all sources takes $O(m \cdot n)$. The BFS visits each cell at most once and examines at most 4 neighbors per cell, so the BFS itself is also $O(m \cdot n)$. The total is $O(m \cdot n)$, independent of the number of sources.

Space complexity is $O(m \cdot n)$ for the distance matrix (or the modified grid) and the BFS queue. In the worst case, all cells could be in the queue simultaneously, though in practice the queue holds at most one "frontier ring" of cells at a time.

For graph problems that are not grid-based, the complexity generalizes to $O(V + E)$, where V is the number of vertices and E is the number of edges, exactly the same as single-source BFS. The multi-source variant does not add any asymptotic overhead.

Recognizing this pattern

You're probably looking at multi-source BFS when:

• The problem has several equal-cost starting points and asks for the distance from any of them to every other cell or node
• You see prompts about rotting, spreading, flooding, infecting, or burning that radiate out from multiple seeds simultaneously
• The question is "how far is each cell from the nearest X" where X appears in many places
• Inverting the search direction (start from the targets rather than the queries) collapses many BFS calls into one

Common templates:

• Grid spread from all sources: push every source cell into the queue at distance zero, then run a level-order BFS. Example: Rotting Oranges.
• Distance to nearest target: seed the queue with every target cell and fill in distances to every other cell. Example: Walls and Gates.
• 0-1 matrix nearest zero: multi-source BFS from every zero to compute the nearest-zero distance for every one. Example: 01 Matrix.
• Bounded region or escape detection: start from the boundary cells and mark anything reachable, then anything unmarked is enclosed. Example: Surrounded Regions.