Rotting Oranges
Problem Statement
You are given an m x n grid where each cell is one of three values: 0 means empty, 1 means a fresh orange, and 2 means a rotten orange.
Every minute, each rotten orange rots all 4-directionally adjacent fresh oranges. Return the minimum number of minutes until no fresh orange remains. If some fresh orange can never rot, return -1.
Input
A 2D integer grid containing empty cells, fresh oranges, and rotten oranges.
Output
An integer: the number of minutes needed to rot every reachable fresh orange, or -1 if impossible.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 <= m, n <= 10 - •
grid[i][j] is 0, 1, or 2
Examples
Example 1
grid = [[2,1,1],[1,1,0],[0,1,1]]
4Example 2
grid = [[2,1,1],[0,1,1],[1,0,1]]
-1Example 3
grid = [[0,2]]
0Learning Objectives
- Recognise simultaneous spread as **multi-source BFS**, not repeated single-source searches.
- Count BFS levels as elapsed minutes while all initial rotten oranges start at distance 0.
- Use a remaining fresh count to decide whether the process succeeded or was blocked.
Intuition
Rot spreads like a wave. If there are several rotten oranges at time 0, they all expand simultaneously. That is the key: you should not BFS from one rotten orange, finish it, then BFS from the next. Doing so would pretend time runs separately for each source and can overcount minutes.
Instead, put all initially rotten cells into the same queue before the BFS starts. They are all distance 0. The first layer of neighbours rots at minute 1, the next layer at minute 2, and so on. This is the same shortest-distance idea as normal BFS, except the queue has multiple starting points.
Tracking fresh oranges turns the end condition into a simple check. Every time a fresh orange is enqueued, immediately mark it rotten and decrement fresh. If fresh reaches 0, the current minute count is enough. If the queue drains while fresh is still positive, those oranges were separated by empty cells and the answer is -1.
Common mistakes
- ×Starting BFS from each rotten orange independently instead of seeding one queue with all sources.
- ×Incrementing minutes after every cell rather than after every BFS layer.
- ×Marking an orange rotten only when it is dequeued, allowing the same fresh orange to be enqueued by multiple neighbours.
- ×Returning the number of processed layers even when fresh oranges remain unreachable.
- ×Returning 1 for a grid that starts with no fresh oranges; the correct answer is 0.
Algorithm Explanation
- Scan the grid once. Count fresh oranges and enqueue every initially rotten cell.
- Run BFS while the queue is non-empty and fresh > 0. Each loop iteration represents one minute and processes exactly the current queue size.
- For each rotten cell in that layer, examine its four neighbours. When a neighbour is fresh, mark it rotten immediately, decrement fresh, and enqueue it for the next minute.
- After the BFS, return minutes if fresh == 0; otherwise return -1.
Solutions
Solution: Multi-source BFS by minute
Seed the queue with all rotten oranges at once, then process one queue layer per minute so the earliest rot time for every cell is computed automatically.
Step-by-step
- The initial scan collects all sources and counts fresh oranges.
- The outer BFS loop runs only while there is still fresh fruit to rot; this prevents an extra minute when the queue contains no useful frontier.
- The current queue size freezes the layer for this minute. Newly rotten oranges are enqueued but processed in the next minute.
- Marking grid[nextRow][nextCol] = 2 before enqueueing prevents duplicate work and duplicate fresh decrements.
O(m · n)
O(m · n)
Every cell is scanned once and each orange enters the queue at most once.
Java implementation
Dry Run
Sample input
grid = [[2,1,1],[1,1,0],[0,1,1]]. Queue starts with all initially rotten cells, so only (0,0) is present at minute 0.
| Minute | Queue at start | Fresh before | Newly rotten | Fresh after |
|---|---|---|---|---|
| 0 | [(0,0)] | 6 | (1,0), (0,1) | 4 |
| 1 | [(1,0), (0,1)] | 4 | (1,1), (0,2) | 2 |
| 2 | [(1,1), (0,2)] | 2 | (2,1) | 1 |
| 3 | [(2,1)] | 1 | (2,2) | 0 |
| 4 | stop | 0 | none | 0 |
The queue represents the current wavefront of rot. The last fresh orange rots during the fourth processed minute, so the answer is 4. A blocked orange would remain fresh after the queue empties, producing -1.
Interview Tips
Lead with multi-source BFS. Say that all rotten oranges are time 0 sources, then each BFS layer is exactly one minute. This framing avoids the most common bug: doing separate BFS runs and combining them incorrectly. Be precise about when minutes increments: after processing the current layer, and only while fresh oranges remain.
Likely follow-ups
- Return the minute at which each orange rots, not just the final time.
- Allow diagonal rotting as well as 4-directional rotting.
- What if some walls block spread but are represented by a separate value?
- How would you solve the same spread process on a general graph instead of a grid?
Similar Problems
Key Takeaways
- Simultaneous spread from many cells is multi-source BFS.
- All initial sources enter the queue before the first minute starts.
- Process queue layers, not individual cells, when time increments by rounds.
- A fresh counter gives a clean success or impossible check at the end.