Rotting Oranges: Multi-Source BFS Pattern

You are given an m x n grid where each cell has one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, a fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains. If it is impossible, return -1.

This is LeetCode 994: Rotting Oranges, and it is one of the best problems for learning multi-source BFS. The technique it teaches applies to any problem where "something spreads outward from multiple starting points simultaneously."

Why this problem matters

Many grid problems ask you to start from a single source and explore outward. Rotting Oranges flips that on its head: you start from multiple sources at once. Every rotten orange spreads to its neighbors simultaneously, not one at a time. This "multi-source" flavor of BFS comes up in problems involving fire spreading, walls expanding, shortest distances from multiple targets, and any scenario where a process radiates outward from several points in parallel.

Once you understand multi-source BFS here, you can apply the same template to problems like "Walls and Gates" (LeetCode 286), "Shortest Bridge" (LeetCode 934), and "01 Matrix" (LeetCode 542).

The key insight

Instead of running BFS from each rotten orange separately, you add all rotten oranges to the queue at the start. Then you process them level by level. Each level of BFS corresponds to one minute. When a level finishes, everything that was fresh and adjacent to something rotten has now turned rotten, and you move on to the next minute.

This is the same as regular BFS, but with multiple starting nodes instead of one. The queue begins with every rotten orange, and each "round" of processing represents one tick of the clock.

The algorithm:

1. Scan the grid. Add every rotten orange to the queue. Count the fresh oranges.
2. Run BFS level by level. For each rotten orange in the current level, rot its fresh neighbors and add them to the queue. Decrement the fresh count.
3. After each level, increment the minute counter.
4. When the queue is empty, check the fresh count. If it is 0, return the minutes elapsed. Otherwise, return -1.

The solution

from collections import deque

def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

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

    if fresh == 0:
        return 0

    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        if queue:
            minutes += 1

    return minutes if fresh == 0 else -1

Let's walk through what each piece does.

The first loop scans the entire grid. It seeds the BFS queue with every rotten orange and counts the total number of fresh oranges. This is the "multi-source" setup: instead of enqueueing one starting node, you enqueue all of them.

The BFS loop processes one full level at a time using the for _ in range(len(queue)) trick. This ensures that all oranges that rotted in the same minute get processed together before the minute counter increments. For each rotten orange, we check its four neighbors. If a neighbor is fresh, we mark it rotten, decrement the fresh count, and add it to the queue for the next round.

The if queue check after the inner loop prevents incrementing minutes after the last batch of rotting (when no new oranges were added). Without it, you would overcount by one.

Finally, if fresh is still positive after BFS finishes, some oranges were unreachable and the answer is -1.

Visual walkthrough

Let's trace through the example grid step by step. Watch how all rotten oranges spread simultaneously, one level of BFS per minute.

Notice that at each minute, every rotten orange from the previous round spreads at the same time. This is the hallmark of multi-source BFS: the wavefront expands uniformly from all sources. By minute 4, every reachable fresh orange has been rotted.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. The initial scan visits every cell once. The BFS also visits each cell at most once, because we mark oranges as rotten (value 2) before enqueueing them, so no cell enters the queue twice. Total work is proportional to the grid size.

Space is O(m * n) in the worst case. If every cell in the grid is a rotten orange, the queue starts with m * n entries. In practice, the queue holds at most the size of the BFS frontier, which is smaller, but the worst case is the full grid.

The building blocks

1. Multi-source BFS initialization

The pattern of seeding a BFS queue with multiple starting nodes instead of one:

queue = deque()
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 2:
            queue.append((r, c))

This is the only difference between single-source and multi-source BFS. Everything else, the level-by-level processing, the neighbor exploration, the visited marking, stays exactly the same. You will reuse this initialization pattern in "Walls and Gates," "01 Matrix," "Shortest Bridge," and any problem that asks for shortest distances from multiple sources.

2. Level-by-level BFS processing

The pattern of processing all nodes at the current depth before moving to the next:

while queue:
    for _ in range(len(queue)):
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if valid(neighbor):
                mark_visited(neighbor)
                queue.append(neighbor)
    depth += 1

This gives you a built-in "clock." Each iteration of the outer while loop is one tick. You see this in level-order tree traversal, shortest path in unweighted graphs, and any BFS problem where you need to track distance or time. The range(len(queue)) snapshot is the key detail. Without it, you lose the level boundaries and cannot track the minute count.

Edge cases

Before submitting, think through these scenarios:

• No fresh oranges: return 0 immediately. Nothing needs to rot.
• No rotten oranges but fresh exist: BFS queue is empty from the start, so nothing spreads. Return -1.
• Fresh orange surrounded by empty cells: unreachable by any rotten orange. Return -1.
• Single cell grid: [[0]] returns 0. [[1]] returns -1. [[2]] returns 0.
• All rotten: every cell is 2. Fresh count is 0. Return 0.
• Large grid, all fresh except one corner rotten: BFS spreads across the entire grid. Minutes equal (rows - 1) + (cols - 1), the Manhattan distance from one corner to the opposite.

From understanding to recall

You have seen how multi-source BFS works: seed the queue with all rotten oranges, process level by level, and count the minutes. The logic is clean and the code is short. But writing it from scratch under interview pressure is a different challenge.

The details that trip people up are subtle. Do you increment minutes before or after processing a level? Do you check if queue or if fresh? Do you return minutes or minutes - 1? These are not conceptual gaps. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice writing the multi-source BFS initialization, the level-by-level loop, and the termination check from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "something spreads from multiple sources" in a problem description, and the BFS template flows out without hesitation.

Related posts

• Number of Islands - The foundational grid traversal problem that teaches DFS flood fill on a 2D grid
• Pacific Atlantic Water Flow - Multi-source BFS from ocean borders, applying the same "start from multiple sources" idea
• Shortest Bridge - Combines flood fill to find an island with multi-source BFS to find the shortest path to another

CodeBricks breaks Rotting Oranges into its multi-source BFS initialization and level-by-level processing building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a BFS problem shows up in your interview, you do not think about it. You just write it.