Infection Spread Time on a Grid
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Infection Spread Time on a Grid
You are given an `m x n` grid where every cell holds one of three integer values:
- `0` — an empty cell that can never be infected.
- `1` — a healthy (susceptible) cell.
- `2` — an infected cell.
Every minute, any healthy cell (`1`) that is **4-directionally adjacent** (up, down, left, right) to an infected cell (`2`) becomes infected. Infection spreads simultaneously: all cells that can be infected in a given minute become infected at the same time, then the next minute begins.
Return the **minimum number of minutes** that must elapse until no healthy cell remains. If it is impossible for every healthy cell to become infected (some healthy cell is unreachable from any initially infected cell), return `-1`. If there are no healthy cells to begin with, the answer is `0`.
### Example
```
Input:
2 1 1
1 1 0
0 1 1
Output: 4
```
The single initially infected cell at the top-left spreads outward; the bottom-right healthy cell is the last to be infected, at minute 4.
### Follow-up
After solving the 4-directional version, extend your solution so that infection **also spreads diagonally** — i.e. each cell has up to **8 neighbors** (the four orthogonal neighbors plus the four diagonal neighbors). Describe (and, if asked, implement) what changes in your approach and recompute the minimum minutes for the same input under 8-directional spread.
### Constraints & Assumptions
- `1 <= m, n <= 300`.
- `grid[i][j]` is one of `0`, `1`, or `2`.
- There may be zero, one, or many initially infected cells.
- The grid may contain empty cells (`0`) that block infection (infection does not pass through them, and they are never counted as healthy).
- Time and memory should be efficient enough for the maximum grid size; an $O(m \cdot n)$ solution is expected.
### Required Output
- Return a single integer: the minimum number of minutes until no healthy cell remains, or `-1` if some healthy cell can never be infected.
Quick Answer: This question evaluates a candidate's ability to apply multi-source breadth-first search to simulate simultaneous state propagation across a 2D grid. It tests graph traversal, reachability reasoning, and time-complexity awareness — core competencies commonly assessed in coding interviews for software engineering roles. The follow-up variant on 8-directional spread further probes adaptability and spatial reasoning within the same algorithmic framework.
Infection Spread Time on a Grid (4-Directional)
You are given an `m x n` grid where every cell holds one of three integer values:
- `0` — an empty cell that can never be infected.
- `1` — a healthy (susceptible) cell.
- `2` — an infected cell.
Every minute, any healthy cell (`1`) that is **4-directionally adjacent** (up, down, left, right) to an infected cell (`2`) becomes infected. Infection spreads simultaneously: all cells that can be infected in a given minute become infected at the same time, then the next minute begins.
Return the **minimum number of minutes** that must elapse until no healthy cell remains. If it is impossible for every healthy cell to become infected (some healthy cell is unreachable from any initially infected cell), return `-1`. If there are no healthy cells to begin with, return `0`.
This is a multi-source BFS: enqueue every initially infected cell at level 0, then expand outward one minute (one BFS layer) at a time. The answer is the number of layers needed to consume every healthy cell; if any healthy cell remains after the queue drains, return `-1`.
Constraints
- 1 <= m, n <= 300
- grid[i][j] is one of 0, 1, or 2
- There may be zero, one, or many initially infected cells
- Empty cells (0) block infection and are never counted as healthy
- An O(m * n) solution is expected
Examples
Input: ([[2,1,1],[1,1,0],[0,1,1]],)
Expected Output: 4
Explanation: Single infected cell at top-left; the bottom-right healthy cell is last, infected at minute 4.
Input: ([[2,1,1],[0,1,1],[1,0,1]],)
Expected Output: -1
Explanation: The healthy cell at (2,0) is walled off by 0s and never gets infected, so return -1.
Hints
- Use multi-source BFS: seed the queue with EVERY initially infected cell at once, not one at a time.
- Process the queue one BFS layer per minute. Counting layers (not total nodes) gives you the elapsed minutes.
- Track the number of remaining healthy cells. If it's already 0, the answer is 0; if it's still > 0 after the queue drains, return -1.
- Empty cells (0) are walls — never spread into them and never count them as healthy.
Infection Spread Time on a Grid (8-Directional Follow-up)
Follow-up to the 4-directional version. Same grid encoding:
- `0` — an empty cell that can never be infected.
- `1` — a healthy (susceptible) cell.
- `2` — an infected cell.
Now infection **also spreads diagonally**: each cell has up to **8 neighbors** — the four orthogonal neighbors (up, down, left, right) PLUS the four diagonal neighbors. Every minute, any healthy cell adjacent (in any of the 8 directions) to an infected cell becomes infected, simultaneously.
Return the **minimum number of minutes** until no healthy cell remains, or `-1` if some healthy cell can never be infected. Return `0` if there are no healthy cells to begin with.
The approach is identical to the 4-directional case — multi-source BFS — and the ONLY change is the neighbor direction set: replace the 4 orthogonal offsets with all 8 offsets. Because diagonal moves are allowed, infection can flow around some 0 walls that would block the 4-directional version, so the same input often finishes in fewer minutes.
Constraints
- 1 <= m, n <= 300
- grid[i][j] is one of 0, 1, or 2
- Infection spreads to all 8 neighbors (4 orthogonal + 4 diagonal)
- Empty cells (0) block infection and are never counted as healthy
- An O(m * n) solution is expected
Examples
Input: ([[2,1,1],[1,1,0],[0,1,1]],)
Expected Output: 2
Explanation: With diagonals, (0,0) reaches (1,1) at minute 1, and (1,1) reaches the bottom-right via a diagonal at minute 2 — faster than the 4-directional answer of 4.
Input: ([[2,1,1],[0,1,1],[1,0,1]],)
Expected Output: 2
Explanation: Diagonal moves let infection reach (2,0) and (2,2) (walled off in the 4-dir version), finishing at minute 2.
Hints
- The algorithm is unchanged from the 4-directional version — only the direction list grows from 4 offsets to all 8.
- Diagonal offsets are (-1,-1), (-1,1), (1,-1), (1,1); add these to the orthogonal four.
- Because diagonals let infection slip past some 0 walls, the same grid can finish faster than under 4-directional spread.
- A healthy cell still returns -1 if NO infected cell can reach it via any 8-directional path through non-empty cells.