Minutes Until Rot Spreads to Every Fresh Cell in a Grid
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A rectangular grid shows the cells of a crate of fruit. Each cell is empty, holds a fresh piece of fruit, or holds a rotten piece. Rot spreads once per minute: every fresh piece that shares an edge with a rotten piece becomes rotten, and all pieces that rot in the same minute do so simultaneously. Return the minimum number of minutes after which no fresh fruit remains, or `-1` if some fresh fruit can never rot.
### Function Signature
```python
def minutes_until_no_fresh(grid: list[list[int]]) -> int:
```
### Rules
- `grid[r][c]` is `0` for an empty cell, `1` for fresh fruit and `2` for rotten fruit.
- Two cells are adjacent only when they share an edge (up, down, left or right). Diagonal cells are not adjacent, and rot does not pass through empty cells or across the edge of the grid.
- Minute 0 is the grid as given. In minute `k` (`k >= 1`), every fresh cell adjacent to a cell that was rotten at the end of minute `k - 1` becomes rotten. A cell that rots in minute `k` spreads rot only from minute `k + 1` on.
- Return the smallest `k >= 0` such that no fresh cell remains at the end of minute `k`. If the grid contains no fresh cell at the start, return `0`, whether or not it contains a rotten cell. If at least one fresh cell never becomes rotten, return `-1`.
### Constraints
- `1 <= len(grid) <= 300` and `1 <= len(grid[r]) <= 300`; all rows have the same length.
- Every cell is `0`, `1` or `2`.
- The result is `-1` or an integer from `0` up to at most `len(grid) * len(grid[0]) - 1`.
### Examples
**Example 1**
```text
Input: grid = [[2, 1, 0], [1, 1, 1], [0, 0, 1]]
Output: 4
```
```text
minute 0 minute 1 minute 2 minute 3 minute 4
2 1 0 2 2 0 2 2 0 2 2 0 2 2 0
1 1 1 2 1 1 2 2 1 2 2 2 2 2 2
0 0 1 0 0 1 0 0 1 0 0 1 0 0 2
```
The rot starts in the top-left corner. The cell in row 1, column 1 rots only in minute 2, because its neighbours are still fresh at the end of minute 0. The last fresh cell, in the bottom-right corner, rots in minute 4.
**Example 2**
```text
Input: grid = [[1, 0, 2], [0, 1, 1]]
Output: -1
```
The fresh cell in row 0, column 0 has only empty neighbours, so it never rots, even though the other two fresh cells rot in minutes 1 and 2.
**Example 3**
```text
Input: grid = [[2, 1, 1, 1, 2]]
Output: 2
```
Both rotten cells spread at the same time: columns 1 and 3 rot in minute 1 and column 2 rots in minute 2.
Overview: Given a grid of empty cells, fresh fruit and rotten fruit, where rot spreads each minute to edge-adjacent fresh fruit, return the number of minutes until no fresh fruit remains, or -1 if some never rots. Tests simultaneous spreading from many sources and detection of unreachable cells.
A rectangular grid shows the cells of a crate of fruit. Each cell is empty, holds a fresh piece of fruit, or holds a rotten piece. Rot spreads once per minute: every fresh piece that shares an edge with a rotten piece becomes rotten, and all pieces that rot in the same minute do so simultaneously.
Implement `minutes_until_no_fresh(grid)`, which returns the minimum number of minutes after which no fresh fruit remains, or `-1` if some fresh fruit can never rot.
**Rules**
- `grid[r][c]` is `0` for an empty cell, `1` for fresh fruit and `2` for rotten fruit.
- Two cells are adjacent only when they share an edge (up, down, left or right). Diagonal cells are not adjacent, and rot does not pass through empty cells or across the edge of the grid (the last cell of one row and the first cell of the next row do not share an edge).
- Minute 0 is the grid as given. In minute `k` (`k >= 1`), every fresh cell adjacent to a cell that was rotten at the end of minute `k - 1` becomes rotten. A cell that rots in minute `k` spreads rot only from minute `k + 1` on.
- Return the smallest `k >= 0` such that no fresh cell remains at the end of minute `k`. If the grid contains no fresh cell at the start, return `0`, whether or not it contains a rotten cell. If at least one fresh cell never becomes rotten, return `-1`.
**Example 1**
```
Input: grid = [[2, 1, 0], [1, 1, 1], [0, 0, 1]]
Output: 4
```
The rot starts in the top-left corner. Row 0, column 1 and row 1, column 0 rot in minute 1. The cell in row 1, column 1 rots only in minute 2, because its neighbours are still fresh at the end of minute 0. Row 1, column 2 rots in minute 3, and the last fresh cell, in the bottom-right corner, rots in minute 4.
**Example 2**
```
Input: grid = [[1, 0, 2], [0, 1, 1]]
Output: -1
```
The fresh cell in row 0, column 0 has only empty neighbours, so it never rots, even though the other two fresh cells rot in minutes 1 and 2.
**Constraints**
- `1 <= len(grid) <= 300` and `1 <= len(grid[r]) <= 300`; all rows have the same length.
- Every cell is `0`, `1` or `2`.
- The result is `-1` or an integer from `0` up to at most `len(grid) * len(grid[0]) - 1` (at most 89,999), so it always fits in a 32-bit signed integer.
Constraints
- 1 <= len(grid) <= 300
- 1 <= len(grid[r]) <= 300, and all rows have the same length
- Every cell grid[r][c] is 0 (empty), 1 (fresh) or 2 (rotten)
- The result is -1 or an integer from 0 up to at most len(grid) * len(grid[0]) - 1 (at most 89,999), so it fits in a 32-bit signed integer
Examples
Input: ([[0]],)
Expected Output: 0
Explanation: Minimum 1x1 grid holding one empty cell: no fresh fruit at the start, so 0.
Input: ([[2]],)
Expected Output: 0
Explanation: Minimum 1x1 grid holding one rotten cell and no fresh fruit: 0.
Hints
- A cell that rots during minute k only starts spreading in minute k + 1, so keep the cells that rotted this minute apart from the ones that were already rotten when the minute began.
- Count the fresh cells first: with none the answer is 0, and if the rot stops spreading while some are still fresh the answer is -1.
- Every rotten cell spreads at the same time, so the answer is the minute in which the last fresh cell rots, not a total over the separate rotten cells.