Rotting Oranges
Asked at Amazon, Microsoft, Databricks, Salesforce, Uber, OpenAI
Problem
In a grid, each cell can be fresh, rotten, or empty. Every minute, rotten oranges spread to adjacent fresh oranges. Return the minimum number of minutes until no fresh oranges remain. This is a classic multi-source BFS problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Databricks | Medium | View all Databricks questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Uber | Medium | View all Uber questions → |
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
This is multi-source BFS — all rotten oranges are starting points simultaneously. Don't run BFS from each one separately; enqueue all of them at the start.
Process the queue layer by layer. Each layer represents one minute of time. Count layers to get the minimum minutes.
Use a counter for fresh oranges. When a fresh orange becomes rotten, decrement. After BFS, if fresh > 0, some oranges are unreachable — return -1.
Visual walkthrough for grid:
[[2,1,1],[1,1,0],[0,1,1]]
Initially: rotten at (0,0), fresh count = 5.
Minute 0: queue = [(0,0)]. Process (0,0): rot (0,1) and (1,0). Queue now: [(0,1),(1,0)]. fresh=3.
Minute 1: process (0,1) → rot (1,1). process (1,0) → rot nothing (down is 0). Queue: [(1,1)]. fresh=2.
Minute 2: process (1,1) → rot (1,2)? No, (1,2)=0. rot (2,1). Queue: [(2,1)]. fresh=1.
Minute 3: process (2,1) → rot (2,2). Queue: [(2,2)]. fresh=0.
Minute 4: queue empty. Result: 3 (minutes 1, 2, 3 did the work).
Optimal Approach
Step 1: Scan the grid. Enqueue all initially rotten oranges. Count fresh oranges.
Step 2: BFS layer by layer. For each layer (one minute):
- Process all currently queued cells
- For each cell, check 4 neighbors
- If neighbor is fresh (1), make it rotten (2), decrement fresh count, enqueue
Step 3: After BFS, if fresh > 0, return -1. Otherwise return minutes.
The key is processing layer by layer — use a for-loop over the current queue size at each minute. Don't mix layers.
Time: O(m × n). Space: O(m × n) for the queue.
What Trips People Up in Real Interviews
Confusing this with DFS. BFS is the right approach because rotting spreads level by level — each level represents one minute. DFS doesn't give you the level order.
Not adding all rotten oranges to the queue initially. Multiple oranges can rot simultaneously at minute 0. Add them all to the queue before starting BFS.
Forgetting to check if any fresh orange remains after BFS. If yes, return -1 (some orange can never rot).
Not counting the minutes correctly. The number of BFS levels is the minutes. Don't count the initial level (minute 0) as a minute.
Treating empty cells (0) the same as fresh cells (1). Empty cells can't be rotted — don't add them to the fresh count and skip them during BFS neighbor exploration.
Solution Code
from collections import deque
def orangesRotting(grid):
q = deque()
fresh = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
while q:
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes - 1 if fresh == 0 else -1Frequently Asked Questions
What is the Rotting Oranges problem?
In a grid, each cell can be fresh, rotten, or empty. Every minute, rotten oranges spread to adjacent fresh oranges. Return the minimum number of minutes until no fresh oranges remain. This is a classic multi-source BFS problem.
How do you solve Rotting Oranges?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Rotting Oranges?
Rotting Oranges is asked at Amazon, Microsoft, Databricks, Salesforce, Uber, OpenAI. It is a medium difficulty problem.
What are common mistakes on Rotting Oranges?
- Confusing this with DFS. BFS is the right approach because rotting spreads level by level — each level represents one minute. DFS doesn't give you the level order.
- Not adding all rotten oranges to the queue initially. Multiple oranges can rot simultaneously at minute 0. Add them all to the queue before starting BFS.
- Forgetting to check if any fresh orange remains after BFS. If yes, return -1 (some orange can never rot).
- Not counting the minutes correctly. The number of BFS levels is the minutes. Don't count the initial level (minute 0) as a minute.
- Treating empty cells (0) the same as fresh cells (1). Empty cells can't be rotted — don't add them to the fresh count and skip them during BFS neighbor exploration.