Rotting Oranges

Difficulty: Hard · Topic: Pathfinding

In a grid, 0 is empty, 1 is a fresh orange, 2 is rotten. Every minute, a rotten orange rots any 4-directionally adjacent fresh orange. Return the number of minutes until no orange is fresh, or -1 if some fresh orange can never rot. This is multi-source BFS — start from all rotten oranges at once.

Examples

oranges_rotting([[2,1,1],[1,1,0],[0,1,1]])
→ 4

oranges_rotting([[2,1,1],[0,1,1],[1,0,1]])
→ -1

The bottom-left orange is isolated.

Target complexity: time O(R·C), space O(R·C)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.