Minutes Until Spoilage Spreads to Every Fresh Item in a Grid
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A storage grid holds perishable items. Each cell is empty (`0`), holds a fresh item (`1`), or holds a spoiled item (`2`). Every minute, each fresh item that shares an edge with a spoiled item becomes spoiled. Return the number of minutes that pass until no fresh item remains, or `-1` if some fresh item can never spoil.
### Function Signature
```python
def minutes_until_all_spoiled(grid: list[list[int]]) -> int:
```
### Rules
- Two cells share an edge when they are next to each other horizontally or vertically; diagonal cells do not share an edge.
- Spreading is simultaneous: an item that spoils during minute `t` starts spoiling its neighbors only during minute `t + 1`.
- If the grid contains no fresh item at the start, return `0`.
- If some fresh item can never become spoiled, return `-1`.
- Otherwise, return the smallest number of minutes after which no cell holds a fresh item.
### Constraints
- `1 <= len(grid) <= 500` and `1 <= len(grid[0]) <= 500`; every row has the same length.
- Every `grid[r][c]` is `0`, `1` or `2`.
### Examples
**Example 1**
```text
Input: grid = [[2, 1, 0], [1, 1, 0], [0, 1, 1]]
Output: 4
```
Minute 1 spoils the items at `(0, 1)` and `(1, 0)`, minute 2 the item at `(1, 1)`, minute 3 the item at `(2, 1)`, and minute 4 the item at `(2, 2)`.
**Example 2**
```text
Input: grid = [[2, 1, 1, 1, 2]]
Output: 2
```
Both spoiled items spread at once: minute 1 spoils `(0, 1)` and `(0, 3)`, and minute 2 spoils `(0, 2)`.
**Example 3**
```text
Input: grid = [[1, 0, 2]]
Output: -1
```
The fresh item at `(0, 0)` has only the empty cell `(0, 1)` as a neighbor, so it never spoils.
Overview: Fresh items in a grid spoil one minute after an edge-adjacent item spoils, with every item spreading at the same time. Return how many minutes pass until no fresh item remains, or -1 if one can never spoil. Tests simultaneous spread from several sources, minute-by-minute grid simulation and detection of unreachable cells.
Read the full Amazon Software Engineer interview experience this question came from
A storage grid holds perishable items. Each cell `grid[r][c]` is empty (`0`), holds a fresh item (`1`), or holds a spoiled item (`2`). Every minute, each fresh item that shares an edge with a spoiled item becomes spoiled. Return the number of minutes that pass until no fresh item remains, or `-1` if some fresh item can never spoil.
Rules:
- Two cells share an edge when they are next to each other horizontally or vertically; diagonal cells do not share an edge.
- Spreading is simultaneous: an item that spoils during minute `t` starts spoiling its neighbors only during minute `t + 1`.
- If the grid contains no fresh item at the start, return `0`.
- If some fresh item can never become spoiled, return `-1`.
- Otherwise, return the smallest number of minutes after which no cell holds a fresh item.
The result is a single integer: `-1`, `0`, or a positive minute count smaller than 250,000 (the grid has at most 250,000 cells). It never exceeds 2^31 - 1, so a 32-bit `int` is enough in every language.
Example 1:
Input: grid = [[2, 1, 0], [1, 1, 0], [0, 1, 1]]
Output: 4
Explanation: Minute 1 spoils the items at (0, 1) and (1, 0), minute 2 the item at (1, 1), minute 3 the item at (2, 1), and minute 4 the item at (2, 2).
Example 2:
Input: grid = [[2, 1, 1, 1, 2]]
Output: 2
Explanation: Both spoiled items spread at once: minute 1 spoils (0, 1) and (0, 3), and minute 2 spoils (0, 2).
Constraints:
- 1 <= len(grid) <= 500 and 1 <= len(grid[0]) <= 500; every row has the same length.
- Every grid[r][c] is 0, 1 or 2.
Constraints
- 1 <= len(grid) <= 500 and 1 <= len(grid[0]) <= 500; every row has the same length.
- Every grid[r][c] is 0, 1 or 2.
Examples
Input: ([[0]],)
Expected Output: 0
Explanation: Minimum 1x1 grid holding only an empty cell: no fresh item at the start, so 0.
Input: ([[2]],)
Expected Output: 0
Explanation: Minimum 1x1 grid holding one spoiled item and no fresh item: 0.
Hints
- Within one minute, only items that were already spoiled when the minute began can spoil their neighbors; an item spoiled during the minute must wait for the next one.
- Several spoiled items spread at the same time, so the answer is not a sum of separate spreads: it is decided by the fresh item that is reached last.
- A fresh item that is cut off from every spoiled item by empty cells or the grid edge never spoils, so check for such items before reporting a time.