Rotting Oranges LeetCode 994 Deep Dive

LeetCode 994 — Rotting Oranges — gives you an m x n grid where each cell is either 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. You must return the minimum number of minutes that must elapse until no fresh orange remains, or -1 if this is impossible.

The problem looks simple on the surface — find the BFS answer — but it contains several subtle traps: the off-by-one on minute counting, unreachable fresh oranges hidden by empty cells, grids with no fresh oranges at all, and the temptation to reach for DFS. This deep dive covers every edge case and the reasoning behind each decision.

Before writing any code, note the key constraint: rotting propagates simultaneously from ALL rotten cells each minute, not sequentially from one cell at a time. This single fact makes multi-source BFS the only correct approach and rules out DFS entirely.

DFS processes one path at a time from a single source. It would visit a fresh orange, mark it rotten, and continue down that path — accumulating a depth that represents "minutes elapsed." But this model is fundamentally wrong for Rotting Oranges, because rotting happens simultaneously from ALL rotten cells every minute, not from one cell in a sequential chain.

Consider a grid with two rotten oranges at opposite corners and a fresh orange equidistant from both. DFS from one rotten cell would traverse the entire path to that fresh orange, counting many minutes. DFS from the other rotten cell would do the same. But in reality both rotten oranges are spreading simultaneously, so the fresh orange rots in just 1 minute. DFS cannot model this parallel propagation.

BFS level-order traversal is the correct model: each BFS level corresponds to exactly one minute of simultaneous rotting. All cells at distance 1 from any rotten source become rotten in minute 1, all cells at distance 2 become rotten in minute 2, and so on. The BFS level is the physical time elapsed.

The setup phase scans the entire grid exactly once and performs two tasks simultaneously: enqueueing all initially rotten cells as starting points and counting all fresh oranges. This single scan is crucial — you must seed the BFS queue with every rotten cell before processing begins, because all rotten cells spread in parallel from minute 1.

After scanning, check the immediate base case: if fresh equals 0, there are no fresh oranges to rot, so return 0 immediately regardless of whether rotten cells exist. This handles grids of all empty cells, grids of all rotten cells, and grids with no oranges at all.

Initialize a minutes counter to 0. The queue now holds all rotten cells as level 0 — the starting state before any time has elapsed. The BFS will process level by level, and minutes will be incremented only when at least one fresh orange is newly infected in a given round.

The BFS loop processes the queue in rounds. At the start of each round, snapshot the current queue size — this is the number of cells at the current BFS level. Process exactly that many cells, then check if any fresh oranges were newly infected during this round. If yes, increment minutes. If no infections occurred, the round was the final cleanup step and should not count as a minute.

For each rotten cell dequeued, check all four neighbors (up, down, left, right). If a neighbor is within bounds and is a fresh orange (value 1), mark it rotten (set to 2), decrement fresh, and enqueue it. The cell is marked before enqueueing to prevent duplicate processing — BFS grids must mark visited cells immediately on discovery, not on processing.

The loop continues until the queue is empty. After the loop, check if fresh equals 0. If yes, return minutes. If fresh is still greater than 0, some oranges were unreachable — return -1. The minutes counter reflects only rounds where actual infection occurred, avoiding the off-by-one that trips many implementations.

All rotten, no fresh: scan finds fresh == 0, return 0 immediately. No BFS needed. This is the most common easy case and must be handled before entering the loop. All fresh, no rotten: after scanning, queue is empty but fresh > 0. The BFS loop never runs. After the loop, fresh > 0, so return -1. The rotten-source check in setup catches this efficiently.

Unreachable fresh oranges isolated by empty cells: this is the trickiest case. BFS runs to completion but some fresh oranges sit in pockets surrounded by empty cells (value 0) with no rotten neighbor path. BFS cannot reach them. After the loop, fresh > 0, so return -1. The only way to detect this is by checking the fresh counter after BFS finishes.

Single cell grids: a 1x1 grid with value 0 returns 0. A 1x1 grid with value 1 returns -1 (fresh, no rotten). A 1x1 grid with value 2 returns 0 (rotten, no fresh). A grid of all empties returns 0. These degenerate cases all fall through the fresh == 0 early return or the post-BFS fresh > 0 check without special handling.

Python: from collections import deque. def orangesRotting(grid): 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 not fresh: return 0. minutes = 0. While queue: infected = 0; for _ in range(len(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 grid[nr][nc]==1: grid[nr][nc]=2; fresh-=1; infected+=1; queue.append((nr,nc)). If infected: minutes+=1. Return 0 if fresh==0 else -1.

Java: public int orangesRotting(int[][] grid) { int rows=grid.length, cols=grid[0].length, fresh=0, minutes=0; Queue<int[]> q=new LinkedList<>(); for(int r=0;r<rows;r++) for(int c=0;c<cols;c++) { if(grid[r][c]==2) q.offer(new int[]{r,c}); else if(grid[r][c]==1) fresh++; } if(fresh==0) return 0; int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}}; while(!q.isEmpty()){ int infected=0,sz=q.size(); for(int i=0;i<sz;i++){ int[] cell=q.poll(); for(int[] d:dirs){ int nr=cell[0]+d[0],nc=cell[1]+d[1]; if(nr>=0&&nr<rows&&nc>=0&&nc<cols&&grid[nr][nc]==1){ grid[nr][nc]=2;fresh--;infected++;q.offer(new int[]{nr,nc}); }}} if(infected>0) minutes++; } return fresh==0?minutes:-1; }

Both implementations: O(m*n) time — every cell is enqueued at most once and processed at most once. O(m*n) space — in the worst case the entire grid is rotten and enqueued simultaneously at the start. The minutes off-by-one is handled by the infected guard. The fresh counter serves double duty: drives the early return and detects unreachable oranges at the end.

Walls and Gates (LeetCode 286) is the closest structural sibling: instead of rotten oranges spreading rot, gate cells (value 0) spread shortest-distance counts to room cells (value INF). Enqueue all gates simultaneously, run multi-source BFS, and each room gets filled with its distance to the nearest gate. Same pattern: multiple sources, parallel propagation, O(m*n) time.

Shortest Path in Binary Matrix (LeetCode 1091) extends the pattern to 8-directional movement on a binary grid, finding the shortest clear path from top-left to bottom-right. Pacific Atlantic Water Flow (LeetCode 417) runs two multi-source BFS traversals — one from Pacific borders and one from Atlantic borders — then intersects the reachable sets. These problems form the multi-source BFS family where BFS level equals distance or time.

The unifying principle across this family: whenever a problem has multiple starting points that spread outward simultaneously — whether it is rot, distance, water flow, or fire — the correct approach is multi-source BFS seeded with all starting points at once. Single-source BFS from each start point separately would be O(k * m * n) where k is the number of sources; multi-source BFS collapses this to O(m * n) regardless of source count.