Compute fruit spoilage time in a grid
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's understanding of graph traversal concepts, grid-based state propagation, and reachability analysis in time-evolving systems.
Constraints
- 1 <= m, n <= 10^3
- grid[i][j] is 0, 1, or 2
- The grid is processed in place; treat the input as mutable.
Examples
Input: ([[2,1,1],[1,1,0],[0,1,1]],)
Expected Output: 4
Explanation: Spoilage spreads outward from the top-left source. The farthest fresh fruit (bottom-right) spoils at minute 4.
Input: ([[2,1,1],[0,1,1],[1,0,1]],)
Expected Output: -1
Explanation: The fresh fruit at the bottom-left corner has no path of fresh/spoiled cells back to a source, so it can never spoil; return -1.
Input: ([[0,2]],)
Expected Output: 0
Explanation: There are no fresh fruits to spoil, so the answer is 0 minutes.
Input: ([[0]],)
Expected Output: 0
Explanation: An empty grid with no fruit at all takes 0 minutes.
Input: ([[1]],)
Expected Output: -1
Explanation: A lone fresh fruit with no spoiled source anywhere can never spoil; return -1.
Input: ([[2,2,2],[2,2,2]],)
Expected Output: 0
Explanation: Every cell is already spoiled, so 0 minutes elapse.
Input: ([[2,1,1,1,1,1,1,1,2]],)
Expected Output: 4
Explanation: Two sources at both ends spread inward; the middle fruits spoil last after 4 minutes (the two sources meet in the center).
Hints
- Run a single breadth-first search seeded with ALL initially-spoiled cells at once, rather than one BFS per source. The number of BFS layers you process equals the answer in minutes.
- Track the count of fresh fruits as you go. Decrement it every time you spoil a neighbor; if the count is still positive after the queue drains, some fruit was unreachable, so return -1.
- Watch the boundary cases: a grid with no fresh fruit at all takes 0 minutes, and increment the minute counter only for layers that actually spoil something.