Grid State After a Given Number of Days of Spoilage Spreading to Neighbors
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
A warehouse floor is modeled as a grid of `m` rows and `n` columns. Each cell holds one of three values:
- `0`: the cell is empty,
- `1`: the cell holds a fresh item,
- `2`: the cell holds a spoiled item.
Spoilage spreads once per day: at the end of each day, every fresh item that shares an edge (up, down, left or right) with an item that was already spoiled at the start of that day becomes spoiled. Given the grid and a number of days, return what the grid looks like after exactly that many days.
### Function Signature
```python
def grid_after_days(grid: list[list[int]], days: int) -> list[list[int]]:
```
### Rules
- Items spoiled during a day start spreading only on the following day.
- Spoilage spreads only between edge-adjacent cells, never diagonally, and never through or into an empty cell. Empty cells stay empty.
- Spoiled items never become fresh again. A fresh item that no spoilage can reach stays fresh forever.
- `days = 0` returns the grid unchanged.
- Return a grid with the same dimensions as the input, containing the value of every cell after exactly `days` days.
### Constraints
- `1 <= m <= 300` and `1 <= n <= 300`, where `m = len(grid)` and every row has length `n`
- Every `grid[r][c]` is `0`, `1` or `2`.
- `0 <= days <= 10^9`
- The output is uniquely determined by the input.
### Examples
**Example 1**
- Input: `grid = [[2, 1, 1, 1], [1, 1, 0, 1], [0, 1, 1, 2]]`, `days = 1`
- Output: `[[2, 2, 1, 1], [2, 1, 0, 2], [0, 1, 2, 2]]`
- Explanation: Two items start spoiled, at row 0, column 0 and at row 2, column 3. After one day each has spoiled its fresh neighbors: row 0, column 1 and row 1, column 0 from the first; row 1, column 3 and row 2, column 2 from the second.
**Example 2**
- Input: `grid = [[2, 1, 1, 1], [1, 1, 0, 1], [0, 1, 1, 2]]`, `days = 3`
- Output: `[[2, 2, 2, 2], [2, 2, 0, 2], [0, 2, 2, 2]]`
- Explanation: On day 2 the remaining four fresh items spoil, so the grid is fully spoiled after two days, and day 3 changes nothing.
**Example 3**
- Input: `grid = [[2, 0, 1], [0, 1, 1]]`, `days = 5`
- Output: `[[2, 0, 1], [0, 1, 1]]`
- Explanation: The spoiled item's only neighbors are empty cells, so spoilage never reaches the fresh items and the grid never changes.
Overview: A grid holds empty cells, fresh items and spoiled items, and each day spoilage spreads from every spoiled item to its edge-adjacent fresh neighbors. Given the grid and a number of days that may be very large, return the grid after exactly that many days. It tests simultaneous multi-source spreading, day-by-day timing, and unreachable cells.
Read the full Capital One Software Engineer interview experience this question came from
