4.20.6 — Rotting Oranges

LeetCode 994 · Medium

The problem

A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, a rotten orange rots each fresh orange directly adjacent to it. Return the number of minutes until no fresh orange remains, or -1 if that never happens.

2 1 1        2 2 1        2 2 2        2 2 2
1 1 0   →    2 1 0   →    2 2 0   →    2 2 0     →  4 minutes
0 1 1        0 1 1        0 2 1        0 2 2

The pattern

Three signals point at BFS, and all three are worth recognising:

• "Every minute" — the process happens in discrete rounds.
• "Adjacent" — each round spreads by exactly one step.
• The answer is a number of steps, not a set of cells.

BFS explores in rings — everything one step away, then everything two steps away — so the ring number is the minute number.

And there are many starting points, since every rotten orange spreads at once. That is multi-source BFS: put every source in the queue before the loop begins, all at distance zero. They then expand together, and each fresh orange is reached by whichever rotten orange is nearest.

No extra machinery. Multi-source BFS is single-source BFS with a fuller initial queue.

The solution

Python

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh = 0

        for r in range(rows):                        # seed ALL sources first
            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                                 # nothing to rot

        minutes = 0
        while queue and fresh > 0:
            minutes += 1
            for _ in range(len(queue)):              # exactly one minute
                r, c = queue.popleft()
                for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2             # mark on ENQUEUE
                        fresh -= 1
                        queue.append((nr, nc))

        return minutes if fresh == 0 else -1

TypeScript

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let queue: Array<[number, number]> = [];
  let fresh = 0;

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }

  if (fresh === 0) return 0;

  let minutes = 0;
  while (queue.length && fresh > 0) {
    minutes++;
    const next: Array<[number, number]> = [];
    for (const [r, c] of queue) {
      for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    queue = next;
  }

  return fresh === 0 ? minutes : -1;
}

Five details, and each is a place people lose marks.

Seed every rotten orange before the loop. Running BFS once per source would be far slower and would need the minimum taken afterwards.

for _ in range(len(queue)) freezes the level, so one iteration of the outer loop is exactly one minute. This is the same line as 4.14.8 Level Order Traversal.

Count the fresh oranges up front, and decrement as they rot. At the end, any left means some were unreachable → -1. Counting them again at the end would also work and costs another pass.

if fresh == 0: return 0 before the loop. A grid with no fresh oranges takes zero minutes, including a completely empty grid. Without this, a grid of only rotten oranges would still run one round and return 1.

while queue and fresh > 0. Stopping as soon as the last orange rots avoids counting one extra minute for the final round that changes nothing. Alternatively, run the loop to exhaustion and return minutes - 1 — but that needs its own guard for the zero case, which is uglier.

Mark on enqueue, not on dequeue. A cell reached by two rotten neighbours in the same minute would otherwise be queued twice.

Complexity

O(rows \times cols) time — every cell enters the queue at most once.

O(rows \times cols) space for the queue.

Where this goes next

Multi-source BFS is a small idea that solves a lot:

• Walls and Gates — distance from every cell to its nearest gate. Identical code with different labels. 4.20.7.
• 01 Matrix — distance from each cell to the nearest zero. Seed every zero.
• As Far from Land as Possible — seed every land cell and take the last ring reached.
• Shortest Bridge — flood one island to find it, then BFS outward from all of it at once until you hit the other.

The tell is always the same: the question is "distance to the nearest X" for many X at once. Seed them all and run BFS once.

What the interviewer will push on

"Why BFS and not DFS?" The answer is a number of steps, and BFS explores by distance so the ring number is the answer. DFS would find a route, not the shortest.

"How do you handle many starting points?" All of them in the queue before the loop.

"How do you know when a minute has passed?" The frozen level size.

"How do you detect the impossible case?" Fresh oranges remaining after the queue drains — they were unreachable.

"What if the grid has no fresh oranges at all?" Zero minutes, and it needs the explicit guard.

"What if rotting spread diagonally too?" Eight neighbours instead of four. Nothing else changes, which is a good demonstration that the algorithm does not care about the geometry.

One thing to volunteer: name the technique — "this is multi-source BFS, so every rotten orange goes into the queue before the first round" — and say that the ring number is the minute. Those two sentences are the whole solution.

Next: 4.20.7 Walls and Gates — the same algorithm, filling in distances instead of counting rounds.