Rotting Oranges

Problem

Supply chain systems track perishable goods in warehouse grids. When a product spoils, it contaminates neighbors within one time step - and multiple spoiled items spread simultaneously. Given a grid of fresh and rotten items, find the minimum time until all perishables are either consumed or spoiled, or report if isolated items can never be reached.

[[2,1,1],   → 4 minutes
 [1,1,0],
 [0,1,1]]
 
[[2,1,1],   → -1 (bottom-left fresh is isolated)
 [0,1,1],
 [1,0,1]]
 
[[0,2]]     → 0 (no fresh oranges)

Solution

Approach: multi-source BFS, seeding every rotten orange at time 0.

All rotten oranges spread at once, so the spread is one BFS wave with many starting points rather than several separate searches. We scan the grid once, enqueue every rotten cell as (row, col, 0), and count the fresh oranges. Pre-loading all sources means the combined frontier expands ring by ring: every cell at distance 1 from any source rots at minute 1, distance 2 at minute 2, and so on. Because each fresh orange is first reached by the nearest rotten one, the minute it is stamped with is its minimum time-to-rot - exactly what we want.

The loop pops a cell and checks its four orthogonal neighbors. A fresh neighbor (grid == 1) is rotted in place by setting it to 2, which doubles as the visited mark, decremented from fresh_count, and enqueued at time + 1. Mutating the grid the instant we enqueue is what stops two rotten neighbors from both queuing the same cell. We track minutes = max(minutes, time + 1) so the answer is the time of the last orange to rot. On [[2,1,1],[1,1,0],[0,1,1]] the wave reaches the bottom-right fresh orange last, at minute 4.

Edge cases: no fresh oranges returns 0 immediately (the fresh_count == 0 guard), even with no rotten ones. If any fresh orange is walled off, fresh_count stays positive after the queue drains and we return -1.

Complexity: O(rows * cols) time and space - each cell is enqueued and processed at most once, and the queue can hold every cell.