Rotting Oranges

Some problems spread outward from many places at once: fire, infection, a signal, rot. The time for the spread to reach a cell is its distance from the nearest source. BFS gives distances level by level — and one small change lets it handle all sources in a single pass.

The problem

A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, each rotten orange turns its fresh neighbours — up, down, left, right — rotten. Return the number of minutes until no fresh orange remains. If some fresh orange can never rot, return -1.

Example 1.

2 1 1 00 1 0 11 1 1 2

Output: 3. After minute 1, three oranges next to the two rotten ones have rotted; after minute 2, three more; the orange in the bottom-left corner rots in minute 3.

Example 2.

2 1 00 0 1

Output: -1. The orange at the bottom right has no path of oranges to the rotten one.

Constraints. The grid is 1 to 300 rows and 1 to 300 columns.

Clarifying questions

• No fresh oranges at the start? The answer is 0.
• Fresh oranges but no rotten ones? Then they never rot: -1.
• Diagonals? No, four directions only.
• May I modify the grid? Assume yes.

Approach 1: the simple way

Simulate the clock. Each minute, scan the whole grid for fresh oranges next to a rotten one, and rot them all together. Stop when a minute changes nothing.

1def oranges_rotting_brute(grid: list[list[int]]) -> int:2    """Simulate minute by minute, rescanning the whole grid every minute."""3    grid = [row[:] for row in grid]4    rows, cols = len(grid), len(grid[0])5    minutes = 06    while True:7        to_rot = [8            (r, c)9            for r in range(rows)10            for c in range(cols)11            if grid[r][c] == 112            and any(grid[nr][nc] == 2 for nr, nc in grid_neighbours(rows, cols, r, c))13        ]14        if not to_rot:15            break16        for r, c in to_rot:17            grid[r][c] = 218        minutes += 119    fresh_left = any(1 in row for row in grid)20    return -1 if fresh_left else minutes

grid_neighbours and DIRECTIONS are the grid helpers from the core-idea lesson. Collecting to_rot first and rotting afterwards matters: an orange that rots this minute must not infect its neighbours in the same minute.

Each minute costs a full scan, O(m × n). The number of minutes can also be O(m × n): lay the oranges out as a long snake that winds through the grid, and the rot advances one cell per minute. That makes the total O((m × n)²). On a 300 × 300 grid a snake holds about 45,000 oranges, so the simulation runs about 45,000 scans of 90,000 cells — around 4 × 10^9 cell checks. Nearly all of that work rereads cells where nothing is happening.

The key insight

Only the cells that rotted last minute can rot anything this minute. So there is no need to rescan the grid: keep those cells in a queue, and look only at their neighbours. That is BFS, and each BFS level is exactly one minute.

The second insight is about the start. Running a separate BFS from each rotten orange and taking the minimum per cell would work, but it costs one full traversal per source. Instead, put every rotten orange in the queue at minute 0. This is multi-source BFS: the BFS spreads from all sources at once, and each orange is reached first by the nearest source — exactly when it would rot.

Approach 2: multi-source BFS

1from collections import deque234def oranges_rotting(grid: list[list[int]]) -> int:5    """Multi-source BFS: every rotten orange starts in the queue at minute 0."""6    rows, cols = len(grid), len(grid[0])7    queue: deque[tuple[int, int]] = deque()8    fresh = 09    for r in range(rows):10        for c in range(cols):11            if grid[r][c] == 2:12                queue.append((r, c))13            elif grid[r][c] == 1:14                fresh += 115    minutes = 016    while queue and fresh:17        minutes += 118        for _ in range(len(queue)):              # one level = one minute19            r, c = queue.popleft()20            for dr, dc in DIRECTIONS:21                nr, nc = r + dr, c + dc22                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:23                    grid[nr][nc] = 2             # rot it now, so it is queued once24                    fresh -= 125                    queue.append((nr, nc))26    return -1 if fresh else minutes

Step by step:

1. One scan: queue every rotten orange and count the fresh ones.
2. While something can still spread (queue) and something is left to rot (fresh), run one minute: pop exactly the oranges that were in the queue when the minute began — len(queue) is read once, at the start.
3. Each fresh neighbour rots immediately, which also marks it visited, so it is queued once.
4. At the end, any fresh orange left was unreachable: -1.

Dry run on Example 1. Cells are (row, column).

fresh is 0, so the loop stops and returns 3. Notice that (1,3) rotted in minute 1 but its only neighbours are empty or already rotten, so it spread nothing in minute 2.

Complexity. Time O(m × n): each cell is queued at most once and checks 4 neighbours. Space O(m × n) for the queue. On the 300 × 300 snake, that is about 360,000 neighbour checks instead of 4 × 10^9.

Edge cases

• No fresh oranges → fresh is 0, the loop never runs, answer 0.
• Fresh oranges, no rotten ones → the queue is empty, the loop never runs, fresh is positive: -1.
• An isolated fresh orange (Example 2) → never reached, -1.
• The last minute → the while queue and fresh condition stops as soon as the last orange rots. Without the fresh check, the loop would run one more empty level and the answer would be 1 too high.

Follow-ups

• "Distance from every cell to the nearest 0" (or the nearest gate, or exit). Same pattern: seed the queue with every 0 and write each cell's level into it.
• "Some oranges rot twice as fast." Levels no longer equal time. Use Dijkstra, or — because the costs are small integers — one queue per minute (a bucket queue).
• "Return the minute each orange rotted." Store minutes in a result grid when each orange is queued.