MediumGraphBFSMulti-source·AmazonFacebook·⚡ Very Frequent
You are given a 2-D matrix grid. Each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, a rotten orange contaminates any adjacent fresh orange (4-directional). Return the minimum minutes until no fresh orange remains, or -1 if impossible.
1 ≤ grid.length, grid[i].length ≤ 10
grid[i][j] is 0, 1, or 2
Example 1
grid[[2,1,1],[1,1,0],[0,1,1]]
Output4
Example 2 (impossible)
grid[[2,1,1],[0,1,1],[1,0,1]]
Output-1
Real-world analogy: Contamination spread
🦠 Outbreak model: Imagine a grid of apartments. Some hold fresh oranges 🍊, some already-rotten ones 🦠, and some are empty. Every minute, every rotten orange simultaneously infects all adjacent fresh ones.
This is multi-source BFS: instead of starting from one cell, we seed the queue with all rotten oranges at once (minute 0). Each BFS level represents one minute. We stop when either the queue empties or all fresh oranges are gone.
The key insight: if we processed each rotten orange separately (single-source BFS repeated), we'd overcount time. Simultaneous spreading requires simultaneous BFS.
Algorithm — Multi-source BFS
1. Count fresh oranges. Enqueue all rotten cells (minute 0). 2. While (fresh > 0 and queue not empty): Process entire current level (= one minute): For each rotten cell → check 4 neighbors If fresh neighbor → mark rotten, enqueue, fresh-- time++ 3. Return time if fresh==0, else -1
if 0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]==1:
grid[row][col]=2; q.append((row,col)); fresh-=1
time += 1
return time if fresh==0 else -1
Common pitfalls
Starting from a single rotten orange
If you run separate BFS from each rotten orange and add up the times, you'll overcount. All rotten oranges must be enqueued before the loop begins — they all spread simultaneously at minute 0.
Incrementing time for each orange, not each level
Time counts BFS levels, not individual orange dequeues. Use for _ in range(len(q)) to exhaust the current level before time += 1.
Returning time when fresh oranges remain
After BFS completes, always check if fresh == 0. If isolated fresh oranges exist (surrounded by empty cells), they can never be reached — return -1.
Off-by-one: time increments even when nothing spreads
Structure the loop as while fresh > 0 and q. If either condition is false before the loop body runs, time won't increment. Don't increment time inside the neighbor loop — only after each full level.
Pattern: Multi-source BFS
Seed the queue with all source cells before BFS starts.
Each BFS level = one time unit. Process len(q) cells per minute.
After BFS, verify all targets were reached — else return -1.
Discussion
…