Simulate Threshold Infection Efficiently
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Simulate Threshold Infection Efficiently
You are given an `m x n` grid, a set of initially infected cells, and an integer threshold `k`. Time advances in synchronous rounds. During a round, every healthy cell with at least `k` infected orthogonal neighbors becomes infected; all such changes take effect together for the next round. Infection is permanent.
Implement:
```python
def infection_times(
rows: int,
cols: int,
initially_infected: list[tuple[int, int]],
k: int,
) -> list[list[int]]:
...
```
Return `0` for initially infected cells, the one-based round in which each later cell becomes infected, and `-1` for cells that never become infected.
## Constraints and Clarifications
- Neighbors share an edge; there is no diagonal or wraparound adjacency.
- Duplicate initial coordinates have no additional effect.
- For `k == 0`, every healthy cell becomes infected in round one.
- A threshold above a cell's degree may leave it healthy forever.
- Avoid rescanning all `rows * cols` cells after every round.
## Hints
- A cell's infected-neighbor count only changes when one of its neighbors becomes infected.
- Queue newly infected cells by round so updates remain synchronous.
- Ensure a cell is enqueued at most once even if several neighbors cross its threshold together.
Quick Answer: Compute infection times on a grid where healthy cells change in synchronous rounds after reaching an infected-neighbor threshold. Use incremental neighbor counts and a round-aware queue to avoid repeatedly scanning the entire grid, including threshold-zero and never-infected cases.
Given a rectangular grid, initial infected coordinates, and a neighbor threshold, return the synchronous infection round for every cell. Initially infected cells have time 0, later infections have one-based rounds, and cells that never reach the orthogonal-neighbor threshold return -1.
Constraints
- Rows and columns are positive integers and initial coordinates must be inside the grid.
- Only orthogonal neighbors contribute; infection is permanent.
- Duplicate initial coordinates have no additional effect.
- For k == 0, every initially healthy cell is infected in round 1.
- Avoid rescanning the entire grid after every round.
Examples
Input: (1, 1, [], 1)
Expected Output: [[-1]]
Explanation: With no infected neighbor, the only cell remains healthy.
Input: (1, 1, [(0, 0)], 1)
Expected Output: [[0]]
Explanation: An initially infected cell has time zero.
Hints
- Maintain each healthy cell's count of infected neighbors.
- Process newly infected cells in chronological queue order.
- Mark a cell when it is enqueued so it cannot be scheduled twice.