Practice: Rotting Oranges
BFS from many starts.
A crate holds fresh and rotten oranges. Every minute, a rotten orange makes its fresh neighbours rot. How many minutes until every orange is rotten? Pause. What spreads out in rings, one minute at a time?

- Fresh and rotten oranges
- Rot spreads each minute
- How long until all rot?
Breadth first from every rotten orange
Breadth first search spreads in rings, so each ring is one minute. The trick is to start from every rotten orange at once, putting them all in the queue together. Each minute, we rot the fresh neighbours of everything in the queue. Run it. Four minutes, and no fresh oranges left.
from collections import deque
def minutes_to_rot(grid):
grid = [list(row) for row in grid]
q = deque((r, c) for r, row in enumerate(grid) for c, v in enumerate(row) if v == "R")
minutes = 0
while q:
spread = False
for _ in range(len(q)):
r, c = q.popleft()
for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == "F":
grid[nr][nc] = "R"; q.append((nr, nc)); spread = True
minutes += spread
fresh = any("F" in row for row in grid)
return -1 if fresh else minutes
print(minutes_to_rot(["RFF", "FF.", ".FF"]))4
Multi source BFS
Starting breadth first search from many places at once is called multi source BFS. It answers, how far is every cell from the nearest starting point. It's used for spreading fires, nearest hospitals, and distances from every exit. It's still O of rows times columns.
| key | value |
|---|---|
| Start | all sources in the queue |
| Each ring | one minute |
| Leftover fresh | impossible, -1 |
| Cost | O(rows × cols) |
Summary
Put every rotten orange in the queue at once, and spread one ring per minute. That's multi source breadth first search. Next, designing a cache.
Key takeaways- All sources first
- One ring per minute
- Check for leftovers