Rotting Oranges (LeetCode 994)

The problem

You get an R x C grid where each cell is 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, each rotten orange rots any fresh orange directly up, down, left or right of it. Return the number of minutes until no fresh orange is left, or -1 if some fresh orange can never be reached.

Input:
2 1 1
1 1 0
0 1 1

Output: 4

The rot spreads from the top-left corner and reaches the bottom-right orange on minute 4.

How to think about it

Start with brute force: simulate minute by minute. Each minute, scan the whole grid, find every fresh orange next to a rotten one, and rot them all at once. Stop when nothing changes. Each scan is O(R·C), and there can be up to O(R·C) minutes (think of a long snake of oranges), so it’s O((R·C)²).

The key insight: “minutes” are BFS levels. The time an orange rots is its shortest distance (in steps) from the nearest rotten orange. Shortest distance on an unweighted grid is BFS. You don’t need to rescan; you only need to look at oranges that just rotted, because only they can rot anything new.

Start from every rotten orange at once. There are several sources, and they all spread at the same speed. So put all of them in the queue at time 0 before starting. That’s multi-source BFS. It behaves as if one imaginary super-source were connected to every rotten orange, and it gives each fresh orange its distance to the closest one.

Count fresh oranges to detect -1. Count them up front, and decrease the count each time one rots. If any remain when the queue empties, they were walled off.

Which pattern is this? BFS, multi-source. The tell is “spreads to neighbours each step” plus “how long until…”, with several starting points.

Approach

1. Scan the grid: push every rotten cell as (r, c, 0) and count fresh.
2. Set t = 0. While the queue is not empty:
   • pop (r, c, t),
   • for each of the four neighbours that is in the grid and fresh: mark it rotten (2), decrease fresh, push it with time t + 1.
3. The last popped t is the time of the last orange to rot.
4. Return t if fresh == 0, else -1.

Solution

from collections import deque

def oranges_rotting(grid):
    R, C = len(grid), len(grid[0]); q = deque(); fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2: q.append((r, c, 0))   # every rotten orange is a source
            elif grid[r][c] == 1: fresh += 1
    t = 0
    while q:
        r, c, t = q.popleft()                     # t of the last pop = answer
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc, t + 1))   # rot it now: no double-queueing
    return t if fresh == 0 else -1
# oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) -> 4

Dry run

On the example grid (cells as (row, col)), starting with fresh = 6:

The last pop has t = 4 and fresh = 0, so the answer is 4.

Complexity

• Time: O(R·C). Each cell enters the queue at most once and checks four neighbours.
• Space: O(R·C). The queue can hold a large share of the grid at once (for example, when most oranges start rotten).

Edge cases and pitfalls

• No fresh oranges at all: the answer is 0, even if there are no rotten ones. [[0]] and [[2]] both return 0.
• Unreachable fresh orange ([[2,1,1],[0,1,1],[1,0,1]]): the bottom-left 1 is cut off, so -1.
• Running a separate BFS from each rotten orange and taking minima is O(k·R·C). Seed them all at once.
• Marking rotten when popped instead of when pushed lets the same orange be queued by two neighbours.
• Off-by-one on the time. Returning t + 1, or counting levels including the initial one, overshoots by a minute.

Related problems

• Walls and Gates (LeetCode 286): multi-source BFS from every gate to fill distances.
• Number of Islands (LeetCode 200): the same grid-as-graph view, with flood fill instead of distances.
• Word Ladder (LeetCode 127): BFS shortest path on a graph you generate on the fly.