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
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 `days` days.
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 (a list of `m` rows, each a list of `n` integers, in the original row and column order), containing the value of every cell after exactly `days` days. The output is uniquely determined by the input.
Note that `days` can be as large as `10^9`, far more than the number of days any grid needs to stop changing, so simulating one day at a time for all `days` days is too slow. All values fit in a signed 32-bit integer.
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.
Constraints
- 1 <= m <= 300, where m = len(grid)
- 1 <= n <= 300, where every row has length n
- grid[r][c] is 0, 1 or 2
- 0 <= days <= 10^9
Examples
Input: ([[2, 1, 1, 1], [1, 1, 0, 1], [0, 1, 1, 2]], 1)
Expected Output: [[2, 2, 1, 1], [2, 1, 0, 2], [0, 1, 2, 2]]
Input: ([[2, 1, 1, 1], [1, 1, 0, 1], [0, 1, 1, 2]], 3)
Expected Output: [[2, 2, 2, 2], [2, 2, 0, 2], [0, 2, 2, 2]]
Hints
- A fresh cell spoils on day d exactly when its shortest edge-adjacent path through fresh cells from some initially spoiled cell has length d.
- Start a breadth-first search from all initially spoiled cells at once; each BFS layer corresponds to one day.
- The spreading stops as soon as a day spoils nothing new, which happens after at most m * n days, so you never need to loop anywhere near 10^9 times.