AI Hints
Home›DSA in Python Tutorial›Trees, Lists and Grids
DSA in Python · Lesson 111 of 132

Practice: Rotting Oranges

BFS from many starts.

⏱ 2 min read▶ Video at 2:12:29🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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?

Practice: Rotting Oranges
From the video: Practice: Rotting Oranges
  • 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.

oranges.pypython
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"]))
Output
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.

keyvalue
Startall sources in the queue
Each ringone minute
Leftover freshimpossible, -1
CostO(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
Next up: Practice: LRU Cache — forget the oldest