Rotting Oranges (Multi-Source BFS)

Difficulty: Medium · Pattern: Graph BFS · Concept: General Coding (DSA) — Core Patterns to Drill

Shortest Path in an Unweighted Graph started BFS from a single node. This variant starts from many nodes simultaneously: a grid of oranges, where 2 = already rotten, 1 = fresh, 0 = empty. Every minute, rot spreads from every currently-rotten cell to its 4-directional fresh neighbors, all at once, in parallel. Find the minimum number of minutes until no fresh orange remains, or -1 if some fresh orange can never be reached.

The technique: seed the BFS queue with every rotten cell at time 0 up front, instead of one starting node — from there it's ordinary level-by-level BFS, and it correctly models simultaneous spreading because all the minute-0 sources get processed before any minute-1 cell does.

Your task: implement minutes_to_rot_all(grid). Do not mutate the input grid.

Implement it yourself

assert minutes_to_rot_all([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert minutes_to_rot_all([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert minutes_to_rot_all([[0, 2]]) == 0
assert minutes_to_rot_all([[1]]) == -1

Next: Right Side View of a Binary Tree