Days Until an Infection Spreads to Everyone on a Grid
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A grid models people standing in fixed positions during an outbreak. Each cell is empty, holds a healthy person, or holds an infected person. Every day, the infection spreads from each infected person to the healthy people directly next to them.
Return the number of days until no healthy person remains, or `-1` if some healthy person can never be infected.
### Function Signature
```python
def days_until_all_infected(grid: list[list[int]]) -> int:
```
### Rules
- `grid[r][c]` is `0` for an empty cell, `1` for a healthy person and `2` for an infected person.
- Two cells are adjacent when they share an edge: `(r, c)` is adjacent to `(r - 1, c)`, `(r + 1, c)`, `(r, c - 1)` and `(r, c + 1)` whenever those cells are inside the grid. Diagonal cells are not adjacent.
- Days are numbered 1, 2, 3 and so on. On each day, every person who is infected at the start of that day infects every healthy person in an adjacent cell. A person infected on a given day starts infecting others only on the next day.
- Empty cells never hold a person, so the infection cannot pass through them.
- Infected people stay infected; nobody recovers and nobody leaves the grid.
- Return the smallest number of days after which no cell holds a healthy person.
- Return `0` if no cell holds a healthy person at the start.
- Return `-1` if at least one healthy person is never infected, including when the grid has healthy people but no infected person.
### Constraints
- `1 <= len(grid) <= 300` and `1 <= len(grid[0]) <= 300`; all rows have the same length.
- Every value in `grid` is `0`, `1` or `2`.
- The returned value lies between `-1` and `len(grid) * len(grid[0])`.
### Examples
**Example 1**
```text
Input: grid = [[2, 1, 0], [1, 1, 1], [0, 0, 1]]
Output: 4
```
Day 1: the infected person at `(0, 0)` infects `(0, 1)` and `(1, 0)`. Day 2: `(1, 1)` is infected. Day 3: `(1, 2)`. Day 4: `(2, 2)`. No healthy person remains after day 4.
**Example 2**
```text
Input: grid = [[1, 0, 2], [1, 0, 1]]
Output: -1
```
Day 1 infects `(1, 2)`. The people at `(0, 0)` and `(1, 0)` are cut off from every infected person by empty cells, so they are never infected.
**Example 3**
```text
Input: grid = [[2, 1, 1, 1, 2]]
Output: 2
```
Day 1: the two infected people infect `(0, 1)` and `(0, 3)`. Day 2: `(0, 2)` is infected.
Overview: A grid holds empty cells, healthy people and infected people, and each day every infected person infects the healthy people in edge-adjacent cells. The task asks for the number of days until nobody healthy remains, or -1 if someone can never be reached, and tests grid traversal, careful day counting and unreachable edge cases.
Read the full OpenAI Software Engineer interview experience this question came from
A grid models people standing in fixed positions during an outbreak. Each cell is empty, holds a healthy person, or holds an infected person. Every day, the infection spreads from each infected person to the healthy people directly next to them.
Implement `days_until_all_infected(grid)`, which returns the number of days until no healthy person remains, or `-1` if some healthy person can never be infected.
### Rules
- `grid[r][c]` is `0` for an empty cell, `1` for a healthy person and `2` for an infected person.
- Two cells are adjacent when they share an edge: `(r, c)` is adjacent to `(r - 1, c)`, `(r + 1, c)`, `(r, c - 1)` and `(r, c + 1)` whenever those cells are inside the grid. Diagonal cells are not adjacent.
- Days are numbered 1, 2, 3 and so on. On each day, every person who is infected at the start of that day infects every healthy person in an adjacent cell. A person infected on a given day starts infecting others only on the next day.
- Empty cells never hold a person, so the infection cannot pass through them.
- Infected people stay infected; nobody recovers and nobody leaves the grid.
### Return value
- Return `0` if no cell holds a healthy person at the start.
- Return `-1` if at least one healthy person is never infected, including when the grid has healthy people but no infected person.
- Otherwise, return the smallest number of days after which no cell holds a healthy person.
### Constraints
- `1 <= len(grid) <= 300` and `1 <= len(grid[0]) <= 300`; all rows have the same length.
- Every value in `grid` is `0`, `1` or `2`.
- The returned value lies between `-1` and `len(grid) * len(grid[0])` (at most 90,000), so it never exceeds 2^31 - 1 and fits in a 32-bit `int` in every language.
### Example 1
```text
Input: grid = [[2, 1, 0], [1, 1, 1], [0, 0, 1]]
Output: 4
```
Day 1: the infected person at `(0, 0)` infects `(0, 1)` and `(1, 0)`. Day 2: `(1, 1)` is infected. Day 3: `(1, 2)`. Day 4: `(2, 2)`. No healthy person remains after day 4.
### Example 2
```text
Input: grid = [[1, 0, 2], [1, 0, 1]]
Output: -1
```
Day 1 infects `(1, 2)`. The people at `(0, 0)` and `(1, 0)` are cut off from every infected person by empty cells, so they are never infected.
Constraints
- 1 <= len(grid) <= 300 and 1 <= len(grid[0]) <= 300; all rows have the same length.
- Every value in grid is 0 (empty cell), 1 (healthy person) or 2 (infected person).
- The returned value lies between -1 and len(grid) * len(grid[0]) (at most 90,000), so it fits in a 32-bit signed integer.
Examples
Input: ([[0]],)
Expected Output: 0
Explanation: Minimum 1x1 grid holding only an empty cell: no healthy person at the start, so 0.
Input: ([[1]],)
Expected Output: -1
Explanation: Minimum 1x1 grid with one healthy person and no infected person: that person is never infected, so -1.
Hints
- Before simulating, settle the two special answers: what to return when nobody is healthy at the start, and what it means if spreading stops while someone is still healthy.
- Everyone infected at the start of a day acts at the same time, and people infected during that day wait until the next day. Keep those two groups apart so a new infection cannot spread on the day it happens.
- A running count of healthy people tells you, as soon as spreading stops, whether anyone was left uninfected.