Virus Containment: Minimum Cuts to Isolate a Spreading Infection on a Grid

Question

## Problem

A virus spreads on an `m x n` grid. Each day, infected cells spread to all 4-connected neighbors. You can quarantine one connected infected region per day by adding walls on its perimeter (each wall segment costs 1). Find the minimum total walls needed to permanently contain the virus.

```python
def min_walls_to_contain(grid: list[list[int]]) -> int:
    # grid[i][j] = 1 if infected, 0 if clean
    # Each day: choose one region to wall off; others spread
    # Return minimum walls used before all clean cells are protected
    pass
```

**Example:**
```
grid = [
  [0,1,0,0,0],
  [1,1,0,0,0],
  [0,0,0,1,1]
]
Day 1: wall the left region (perimeter=6), right region spreads
Day 2: wall the right region (perimeter=...)
Output: total walls used
```

## Follow-ups

1. What BFS/DFS data do you compute per region each day? What is the per-day complexity?
2. How do you decide which region to wall off first — is greedy (largest threat) always optimal?
3. If walling has a budget per day, how does this become a different optimization problem?
4. Extend to a 3D grid — what changes in your region detection?

Virus Containment: Minimum Cuts to Isolate a Spreading Infection on a Grid

Question Details

Full Details

Topics

More from Uber