Rotting Oranges LeetCode 994 — Multi BFS

LeetCode 994 Rotting Oranges gives you an m x n grid where each cell contains one of three values: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten itself. You must return the minimum number of minutes until no fresh orange remains, or -1 if it is impossible.

The key constraint is that all rotten oranges spread simultaneously each minute — not one at a time. This simultaneity is the core of the problem and the reason why a simple DFS or single-source BFS misses the right answer. You need to model the parallel spread correctly.

Important constraints to keep in mind: the grid dimensions are 1 <= m, n <= 10, meaning the grid is small but the pattern scales. There may be zero fresh oranges (return 0 immediately), zero rotten oranges with fresh ones present (return -1), or a mix where some fresh oranges are unreachable.

The defining feature of this problem is that all rotten oranges spread at the exact same time. If you pick any single rotten orange and run BFS from it alone, you get the wrong answer — other rotten oranges would be spreading in parallel, and a fresh orange might actually be reached earlier from a different source.

Multi-source BFS solves this by initializing the queue with all sources simultaneously. Instead of one starting node, you drop every rotten orange into the queue at once before the BFS begins. The first BFS level then represents minute one: all rotten oranges infecting their immediate neighbors. Level two is minute two, and so on. This exactly models the parallel spread described in the problem.

This is identical in structure to the Walls and Gates problem (LeetCode 286), where you initialize the queue with all gate cells at once and spread distance outward. Any time a problem involves multiple sources spreading simultaneously — whether infection, distance, fire, or water — multi-source BFS is the right tool.

The setup phase does two things: it populates the BFS queue with all initially rotten oranges, and it counts all fresh oranges so you know when you are done. This single pass through the grid is all you need before the BFS loop begins.

Scan every cell in the grid. For each cell with value 2 (rotten), add its coordinates (row, col) to the queue. For each cell with value 1 (fresh), increment a freshCount variable. After the scan, if freshCount is zero, return 0 immediately — no fresh oranges means no time needs to pass.

This early return is important. If the grid contains only empty cells and rotten oranges, the answer is 0. Starting the BFS loop with an empty freshCount would still give 0 eventually, but the explicit check makes the logic clearer and avoids unnecessary processing.

The BFS loop processes the queue in rounds, where each complete round represents one minute of elapsed time. At the start of each round, capture the current queue size — this tells you how many rotten oranges are spreading this minute. Process exactly that many cells, then increment the minutes counter.

For each rotten cell dequeued, check all four neighbors (up, down, left, right). If a neighbor is a fresh orange (value 1), mark it as rotten (set to 2), decrement freshCount, and enqueue it so it will spread in the next round. If a neighbor is empty (0) or already rotten (2), skip it.

Continue until the queue is empty. At that point, all reachable fresh oranges have been rotted. The minutes counter holds the total elapsed time. If freshCount is still greater than zero, some oranges were unreachable — return -1.

After the BFS loop completes, the check is simple: if freshCount > 0, there are fresh oranges that were never reachable from any rotten orange. Return -1. Otherwise, return the minutes counter.

The impossible case occurs when fresh oranges are completely surrounded by empty cells with no path to any rotten orange. Since BFS only spreads through 4-adjacent cells and the grid has no diagonal movement, a fresh orange in an isolated island of empty cells will never be reached.

One subtle edge case: if you initialized minutes to 0 and the queue was never empty (meaning there were rotten oranges from the start but no fresh ones), the BFS loop never runs and you return 0. This is correct. Another edge: if you initialized minutes to 0 and the queue starts empty (no rotten oranges, but there are fresh ones), freshCount will still be > 0 after the loop, so you correctly return -1.

In Python, use collections.deque for O(1) popleft. The outer while-loop runs while the queue is non-empty. Inside, snapshot level_size = len(queue), then loop level_size times doing popleft and spreading to neighbors. After the inner loop, if the queue is non-empty (meaning new cells were added this round), increment minutes. This avoids counting the last round when no new oranges rot.

In Java, use a LinkedList as the BFS queue. The structure is identical: outer while(!queue.isEmpty()), snapshot int levelSize = queue.size(), inner for-loop processes levelSize nodes. After the inner for-loop, if (!queue.isEmpty()) minutes++. This pattern cleanly separates level tracking from the BFS mechanics.

Time complexity is O(m * n) — each cell is enqueued and processed at most once. Space complexity is O(m * n) — the queue can hold at most all cells in the worst case where the entire grid starts rotten.

Rotting Oranges belongs to the multi-source BFS family — problems where you initialize the BFS queue with multiple starting nodes and spread outward simultaneously. Recognizing this family lets you apply the same template across many problems without reinventing the approach each time.

Walls and Gates (LeetCode 286) is the closest sibling: fill a grid of rooms and gates, initializing BFS from all gates at once to compute shortest distance from each room to its nearest gate. Pacific Atlantic Water Flow (LeetCode 417) uses multi-source BFS from both ocean borders simultaneously to find cells that can flow to both oceans. Shortest Path in Binary Matrix (LeetCode 1091) is single-source BFS on a grid but uses the same level-by-level distance tracking.

The unifying pattern: whenever a problem says "simultaneously" or "at the same time" or asks for the minimum time/distance where multiple sources spread in parallel, reach for multi-source BFS. Initialize the queue with all sources, then run standard BFS. The level number is your answer.