# The Infection Spread

> It starts with one, and then it spreads.

Canonical URL: <https://datadriven.io/problems/the_infection_spread>

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a 2D grid where 0 = empty, 1 = fresh orange, 2 = rotten orange, simulate minute-by-minute spread in 4 directions. Return the minimum minutes until all fresh oranges become rotten. Return -1 if any fresh orange is unreachable. Return 0 if there are no fresh oranges to begin with.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **multi-source BFS on a grid**, a pattern used in network propagation, signal processing, and geographic analysis. It probes whether a candidate can handle simultaneous wavefront expansion from multiple starting points.

> **Trick to Solving**
>
> Initialize the BFS queue with all rotten oranges at once. Each BFS level represents one minute of propagation. Track the number of minutes and check if any fresh oranges remain at the end.

---

### Break down the requirements

#### Step 1: Find all initially rotten oranges

Scan the grid and enqueue all cells with value 2.

#### Step 2: BFS level by level

Each level represents one minute. For each rotten orange, infect adjacent fresh oranges and add them to the next level.

#### Step 3: Check for remaining fresh oranges

If any cell still has value 1 after BFS completes, return -1.

---

### The solution

**Multi-source BFS with minute tracking**

```python
from collections import deque
def oranges_rotting(grid: list) -> int:
    rows = len(grid)
    cols = len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    if fresh == 0:
        return 0
    minutes = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while queue:
        size = len(queue)
        infected_any = False
        for _ in range(size):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
                    infected_any = True
        if infected_any:
            minutes += 1
    if fresh > 0:
        return -1
    return minutes
```

> **Time and Space Complexity**
>
> **Time:** O(m * n) where m and n are the grid dimensions. Each cell is processed at most once.
> 
> **Space:** O(m * n) for the queue in the worst case.

> **Interviewers Watch For**
>
> Whether you process the queue level by level (for minute counting) vs one-at-a-time. Level-by-level is essential to track time correctly.

> **Common Pitfall**
>
> Incrementing minutes on every dequeue instead of every level. This overcounts the time.

---

## Common follow-up questions

- What if infection could spread diagonally? _(Tests adding 4 more direction vectors for 8-directional BFS.)_
- What if some cells were walls that block infection? _(Tests adding a wall value to the boundary check.)_
- How would you return the final state of the grid? _(Tests returning the modified grid instead of just the count.)_
- What if the grid is very large (millions of cells)? _(Tests memory-efficient BFS with only the frontier stored.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_infection_spread)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.