Rotting Oranges

Problem

You’re given an m x n grid where each cell is:

• 0 — empty,
• 1 — a fresh orange,
• 2 — a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent (up/down/left/right) to a rotten orange becomes rotten. Return the minimum number of minutes that must pass until no fresh orange remains. If some fresh orange can never rot, return -1.

Examples

• grid = [[2,1,1],[1,1,0],[0,1,1]] → 4 — rot spreads outward from the top-left; the last fresh orange (bottom-right) rots at minute 4.
• grid = [[2,1,1],[0,1,1],[1,0,1]] → -1 — the fresh orange at the bottom-left corner is isolated by empty cells and never rots.
• grid = [[0,2]] → 0 — there are no fresh oranges to begin with, so zero minutes pass.

Constraints

• 1 <= m, n <= 10
• Each cell is 0, 1, or 2.
• Rot spreads to all four neighbors simultaneously each minute.

Think about it first

TL;DR

Simultaneous spread from all rotten oranges is a multi-source BFS, where each level is one minute. O(m·n) time, O(m·n) space.

Approach 1 — Brute force (repeated full-grid passes)

Simulate minute by minute. Each minute, scan the whole grid, find every fresh orange next to a rotten one, and rot them, but only after the scan completes so oranges rotted this minute don’t chain-rot in the same minute. Repeat until a full pass changes nothing.

def orangesRotting(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    minutes = 0
    while True:
        to_rot = []
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 2:
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                            to_rot.append((nr, nc))
        if not to_rot:
            break
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    if any(cell == 1 for row in grid for cell in row):
        return -1
    return minutes

Complexity: each minute rescans all m·n cells, and there can be O(m·n) minutes, giving O((m·n)²) time. This is fine for the 10×10 limit, but BFS does it in a single pass.

Approach 2 — Multi-source BFS (optimal)

The rot front expands one ring per minute, which is the level structure of BFS. Seed the queue with all rotten oranges at time 0 (multi-source), process the queue one full level at a time, and count each completed level that produced new infections as one elapsed minute. Track the fresh count to stop early and to detect unreachable oranges.

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(m):
        for c in range(n):
            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)):          # drain exactly one minute's front
            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 < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2          # rot it now (marks visited)
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

Walkthrough (grid = [[2,1,1],[1,1,0],[0,1,1]]): fresh = 6, queue = [(0,0)]. Minute 1: (0,0) rots (0,1) and (1,0), fresh → 4. Minute 2: (0,1) rots (0,2), (1,0) rots (1,1), fresh → 2. Minute 3: (0,2) has no fresh neighbor, (1,1) rots (2,1), fresh → 1. Minute 4: (2,1) rots (2,2), fresh → 0. The loop ends with fresh == 0, so return 4.

Each BFS level is one minute, and the depth of the rot tree from the source is the answer:

flowchart TD
    A["(0,0)"] --> B["(0,1)"]
    A --> C["(1,0)"]
    B --> D["(0,2)"]
    C --> E["(1,1)"]
    E --> F["(2,1)"]
    F --> G["(2,2)"]

Levels: (0,0) at minute 0; (0,1),(1,0) at minute 1; (0,2),(1,1) at minute 2; (2,1) at minute 3; (2,2) at minute 4.

Complexity: every cell is enqueued at most once and its 4 neighbors are scanned once, giving O(m·n) time and O(m·n) space for the queue.

Common pitfalls

• Not fixing the level size. Use for _ in range(len(queue)) to process exactly the oranges present at the start of the minute. Reading len(queue) inside the loop after appending merges future minutes into the current one and undercounts time.
• The no-fresh case. If fresh == 0 at the start, the answer is 0. Handle it before the loop.
• Forgetting the -1 check. Fresh oranges walled off by empty cells never rot. After BFS, any remaining fresh means return -1.
• Off-by-one on minutes. Increment the minute counter before draining a level so the count equals the number of spreading rounds, then use fresh == 0 to validate.

Pattern takeaway

When a process spreads from many sources at once and you need the time or steps for full coverage, use multi-source BFS: enqueue every source at level 0 and count levels. Prefer BFS over DFS whenever the answer is a shortest time or fewest steps, because the level structure is the clock. Pair it with a running “remaining” count to stop early and to detect unreachable targets.