LeetEye LeetEye
Medium Graph Traversal ~5 min

Rotting Oranges

graphs rotting-oranges

Problem

You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples

Example 1
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Orange at (2,0) is isolated.
Key Insight

Start BFS from ALL rotten oranges simultaneously. Each wave = 1 minute.

Multi-source BFS: start from all rotten oranges, spread level by level. Each level = 1 minute. If fresh remain after BFS, return -1.

How to Approach This Problem

Pattern Recognition: When you see keywords like rotting oranges graphs, think Graph Traversal.

Step-by-Step Reasoning

1 BFS is preferred because:
Answer: It naturally processes in "waves" (levels)
Each BFS level = 1 minute. All oranges at distance k rot at minute k.
2 We start BFS from:
Answer: All rotten oranges
Rot spreads FROM rotten oranges. They're our sources.
3 Multi-source BFS means:
Answer: All sources start in queue at once
All rotten oranges start in queue at time 0. BFS processes them together.
4 We track time/minutes by:
Answer: Processing level by level
One level = one minute. After processing all oranges at time t, move to time t+1.
5 We return -1 when:
Answer: Fresh oranges remain after BFS
If any fresh orange is unreachable from rotten ones, it stays fresh forever.

Solution

from collections import deque

def orangesRotting(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    
    # Find all rotten oranges and count fresh
    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
    
    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):  # Process one level
            r, c = queue.popleft()
            for dr, dc in directions:
                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
                    queue.append((nr, nc))
    
    return minutes if fresh == 0 else -1

Complexity Analysis

Time O(m × n)
Space O(m × n)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye