Problem Statement
You are given an m × n grid where:
0 → Empty Cell
1 → Fresh Orange
2 → Rotten Orange
Every minute:
A rotten orange
rots all adjacent
fresh oranges.
Return:
- Minimum time required to rot all oranges.
- Return
-1if impossible.
Brute Force Intuition
In an interview, you can explain it like this:
Simulate the process minute by minute. In every minute, scan the entire grid and rot adjacent fresh oranges.
Since the grid is scanned repeatedly, many cells are visited multiple times.
Complexity
- Time Complexity: O((M × N)²)
- Space Complexity: O(1)
Brute Force Idea
Repeat
↓
Traverse Entire Grid
↓
Rot Adjacent Fresh Oranges
↓
Continue Until
No Change
Moving Towards the Optimal Approach
Notice something important.
Initially:
Multiple Rotten Oranges
start spreading simultaneously.
Instead of processing one rotten orange after another,
we should process:
All Rotten Oranges Together.
This is exactly:
Multi-Source BFS
Pattern Recognition
Whenever you see:
- Spread Infection
- Fire Spread
- Minimum Time
- Shortest Distance from Multiple Sources
Think:
Multi-Source BFS
Key Observation
Instead of pushing only one source into the queue,
push:
Every Rotten Orange
at time:
0
Then BFS naturally processes oranges level by level.
Each level represents:
One Minute
Optimal Approach
Step 1
Traverse the grid.
Push every rotten orange into the queue.
Count fresh oranges.
Step 2
Run BFS.
For every rotten orange:
Visit 4 Directions
↓
Rot Fresh Orange
↓
Push into Queue
Step 3
If all fresh oranges become rotten:
Return Time
Otherwise:
Return -1
Optimal Java Solution
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2) {
q.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0)
return 0;
int minutes = 0;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!q.isEmpty()) {
int size = q.size();
boolean rotten = false;
for (int i = 0; i < size; i++) {
int[] cell = q.poll();
int r = cell[0];
int c = cell[1];
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 &&
nc >= 0 &&
nr < rows &&
nc < cols &&
grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
rotten = true;
q.offer(new int[]{nr, nc});
}
}
}
if (rotten)
minutes++;
}
return fresh == 0
? minutes
: -1;
}
}
Dry Run
Input
2 1 1
1 1 0
0 1 1
Initially:
Queue:
(0,0)
Fresh:
6
Minute 1
Rot:
2 2 1
2 1 0
0 1 1
Queue:
(0,1)
(1,0)
Minute 2
Rot:
2 2 2
2 2 0
0 1 1
Queue:
(0,2)
(1,1)
Minute 3
Rot:
2 2 2
2 2 0
0 2 1
Minute 4
Rot:
2 2 2
2 2 0
0 2 2
Fresh:
0
Answer:
4
Why Multi-Source BFS Works?
All rotten oranges spread simultaneously.
BFS naturally processes:
Level 0
↓
Level 1
↓
Level 2
Each BFS level corresponds to:
One Minute
Thus, the first time a fresh orange is reached is also the minimum time needed to rot it.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(M × N) |
| Space Complexity | O(M × N) |
Interview One-Liner
Treat every initially rotten orange as a BFS source and spread the infection level by level to compute the minimum time required to rot all fresh oranges.
Pattern Learned
Multiple Sources
+
Minimum Time
↓
Multi-Source BFS
Similar Problems
- Rotten Oranges
- Walls and Gates
- 01 Matrix
- Nearest Exit in Maze
- Shortest Path in Binary Matrix
- Distance of Nearest Cell Having 1
Memory Trick
Think:
All Rotten Oranges
↓
Push into Queue
↓
Spread Together
↓
Each BFS Level
=
One Minute
Mental Model
One Source
↓
Normal BFS
--------------------
Many Sources
↓
Multi-Source BFS
Whenever you hear:
"Spread simultaneously", "Minimum time to infect", or "Multiple starting points"
your brain should immediately think:
Multi-Source BFS