Rotting oranges: minutes until every fresh cell spoils

A grid holds empty cells, fresh fruit and spoiled fruit. Every minute, each fresh fruit next to a spoiled one (up, down, left or right) spoils. Return the number of minutes until no fresh fruit is left, or -1 if some fresh fruit can never spoil. Explain why your algorithm is correct and give its time and space.

Interface

Unless you agree on a different interface with the interviewer, assume:

• minutes_to_spoil(grid: list[list[int]]) -> int — 0 is empty, 1 fresh, 2 spoiled.

Example

minutes_to_spoil([[2, 1, 1],
                  [1, 1, 0],
                  [0, 1, 1]])   ->  4
minutes_to_spoil([[2, 1, 1],
                  [0, 1, 1],
                  [1, 0, 1]])   ->  -1   # the bottom-left fruit is cut off by empty cells
minutes_to_spoil([[0, 2]])      ->  0    # no fresh fruit at the start
minutes_to_spoil([[2, 1, 0, 1, 2]])  ->  1   # two sources spread at the same time

Constraints

• 1 <= rows, cols <= 1000; every cell is 0, 1 or 2.
• The grid may be modified in place.

Clarifying questions

• Do diagonal neighbours count?
• What should a grid with no fresh fruit return, and one with fresh fruit but no spoiled fruit?
• May the input grid be modified?

What a strong answer covers

• Multi-source breadth-first search: put every spoiled cell in the queue at minute 0, count the fresh cells, and process the queue one level per minute.
• Correctness: each fruit spoils at its shortest grid distance to the nearest initial spoiled cell, which is exactly the BFS level it is reached at; anything never reached is in a region with no source, so the answer is -1.
• Counting minutes only for levels that spoil something, so the answer is not off by one.
• O(rows · cols) time and space; why running one BFS per source would be slower.
• Edge cases: no fresh fruit, no spoiled fruit, a single cell.

Follow-ups

• Return the minute at which each cell spoils.
• Some cells are walls that also block spreading, or fruit spoils only after two spoiled neighbours.
• The grid is too large for memory and arrives row by row.