994. Rotting Oranges
Asked at Amazon, Microsoft, Databricks, Salesforce and 5 more
Difficulty
Medium
Time
O(m * n)
Space
O(m * n)
Pattern
Breadth-First Search
Companies
9
Problem
You are given a grid of cells. Each cell is one of three things: 0 means the cell is empty, 1 means there is a fresh orange there, and 2 means there is a rotten orange there.
Every minute, rot spreads. Any fresh orange that shares an edge (up, down, left, right — not diagonal) with a rotten orange becomes rotten. All of this happens at the same time each minute.
Return the number of minutes needed until no fresh orange is left. If some fresh orange can never be reached by the rot, return -1 instead. If there are no fresh oranges at the start, the answer is 0.
Rot spreads one step per minute
Constraints
- ●
m == grid.length - ●
n == grid[i].length - ●
1 <= m, n <= 10 - ●
grid[i][j] is 0, 1, or 2
Examples
grid = [[2,1,1],[1,1,0],[0,1,1]]4grid = [[2,1,1],[0,1,1],[1,0,1]]-1grid = [[0,2]]0Asked At
9 companies| 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 → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| Anduril | Medium | View all Anduril questions → |
| Flipkart | Medium | View all Flipkart 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.
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.
Multi-source BFS, layer by layer
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
O(m * n) timefrom 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 runs in O(m * n) time and O(m * n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Rotting Oranges?
Rotting Oranges is asked at Amazon, Microsoft, Databricks, Salesforce, Uber, OpenAI, Goldman Sachs, Anduril, Flipkart. 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.