# LeetCode 749: Contain Virus

## Problem Restatement

We are given a 2D grid representing infected and uninfected cells.

Each cell is one of:

| Value | Meaning |
|---:|---|
| `0` | Uninfected |
| `1` | Infected |
| `-1` | Quarantined infected region |

Every night:

1. Each infected region spreads to neighboring uninfected cells.
2. We may choose exactly one infected region to quarantine.
3. Quarantining a region requires building walls along its border.
4. A quarantined region no longer spreads.

We always quarantine the region that would infect the largest number of uninfected cells during the next spread.

We must return the total number of walls built.

The official problem defines infection spread through 4-directional adjacency and asks us to repeatedly quarantine the most threatening region. ([leetcode.com](https://leetcode.com/problems/contain-virus/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary infection grid |
| Output | Total walls built |
| Spread direction | Up, down, left, right |
| Quarantined region | Marked permanently and no longer spreads |
| Daily choice | Quarantine the region threatening the most cells |

Example function shape:

```python
def containVirus(isInfected: list[list[int]]) -> int:
    ...
```

## Examples

### Example 1

```python
isInfected = [
    [0, 1, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0],
]
```

There are two infected regions.

One threatens more uninfected cells than the other.

We quarantine that larger-threat region first, then let the other region spread.

The process continues until no region can spread.

The final answer is:

```python
10
```

### Example 2

```python
isInfected = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
]
```

The center cell is surrounded.

We need walls around all four sides.

The answer is:

```python
4
```

### Example 3

```python
isInfected = [
    [1, 1, 1, 0, 0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 0, 0],
]
```

The simulation repeatedly quarantines the most dangerous region.

The answer is:

```python
13
```

## First Thought: Spread Everything Greedily

A simple idea is:

1. Find infected regions.
2. Spread them.
3. Quarantine something afterward.

But the order matters.

We must quarantine before the spread, and specifically quarantine the region threatening the most uninfected cells.

So each simulation round needs:

1. Identify all infected regions.
2. Measure their future threat.
3. Quarantine the most dangerous one.
4. Spread all remaining regions.

This is a simulation problem with repeated connected-component analysis.

## Key Insight

Each day, every infected region needs three pieces of information:

| Information | Purpose |
|---|---|
| Region cells | Needed for quarantine and spreading |
| Frontier cells | Uninfected cells the region could infect next |
| Required walls | Number of border walls needed |

We can discover all three with DFS or BFS.

Then:

1. Choose the region with the largest frontier.
2. Add its wall count to the answer.
3. Mark that region as quarantined.
4. Let every other region infect its frontier cells.

Repeat until no region can spread anymore.

## Algorithm

Repeat forever:

### Step 1: Find All Regions

Run DFS over all infected cells.

For each connected region, collect:

- infected cells,
- frontier uninfected cells,
- required wall count.

### Step 2: Stop Condition

If no region can spread, stop.

### Step 3: Choose Region To Quarantine

Pick the region with the largest frontier size.

Add its wall count to the answer.

Mark all cells in that region as:

```python
-1
```

### Step 4: Spread Remaining Regions

For every non-quarantined region:

- infect every frontier cell.

Repeat.

## Correctness

Each DFS discovers exactly one connected infected region because it visits all 4-directionally connected infected cells.

For every region, the algorithm computes:

- all cells belonging to the region,
- all neighboring uninfected frontier cells,
- the exact number of bordering walls needed.

The frontier size correctly measures how many new cells the region would infect during the next spread step. Therefore selecting the region with the largest frontier matches the problem rule.

Marking the quarantined region as `-1` prevents it from spreading in future rounds, which matches the quarantine behavior.

All remaining regions infect exactly their frontier cells, which matches the overnight spread rule.

The process repeats until no frontier exists, meaning no region can infect any new cell. At that point the infection can no longer spread, so the simulation is complete.

Since every round exactly follows the required quarantine and spread rules, the total accumulated wall count is correct.

## Complexity

Let:

```python
m = number of rows
n = number of columns
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O((m * n)^2)` worst case | Many rounds may rescan the whole grid |
| Space | `O(m * n)` | DFS visited states and region storage |

The constraints are small enough for simulation.

## Implementation

```python
class Solution:
    def containVirus(self, isInfected: list[list[int]]) -> int:
        rows = len(isInfected)
        cols = len(isInfected[0])

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        total_walls = 0

        while True:
            visited = set()

            regions = []
            frontiers = []
            walls_needed = []

            for r in range(rows):
                for c in range(cols):
                    if isInfected[r][c] != 1:
                        continue

                    if (r, c) in visited:
                        continue

                    stack = [(r, c)]

                    region = []
                    frontier = set()
                    walls = 0

                    visited.add((r, c))

                    while stack:
                        x, y = stack.pop()

                        region.append((x, y))

                        for dx, dy in directions:
                            nx = x + dx
                            ny = y + dy

                            if not (0 <= nx < rows and 0 <= ny < cols):
                                continue

                            if isInfected[nx][ny] == 1:
                                if (nx, ny) not in visited:
                                    visited.add((nx, ny))
                                    stack.append((nx, ny))

                            elif isInfected[nx][ny] == 0:
                                frontier.add((nx, ny))
                                walls += 1

                    regions.append(region)
                    frontiers.append(frontier)
                    walls_needed.append(walls)

            if not frontiers:
                break

            max_index = 0

            for i in range(1, len(frontiers)):
                if len(frontiers[i]) > len(frontiers[max_index]):
                    max_index = i

            if len(frontiers[max_index]) == 0:
                break

            total_walls += walls_needed[max_index]

            for x, y in regions[max_index]:
                isInfected[x][y] = -1

            for i in range(len(regions)):
                if i == max_index:
                    continue

                for x, y in frontiers[i]:
                    isInfected[x][y] = 1

        return total_walls
```

## Code Explanation

Each simulation round starts by finding all active infected regions.

We track visited infected cells:

```python
visited = set()
```

For each region we store:

```python
regions
frontiers
walls_needed
```

The DFS collects connected infected cells:

```python
if isInfected[nx][ny] == 1:
```

When we see an uninfected neighbor:

```python
elif isInfected[nx][ny] == 0:
```

that cell becomes part of the frontier:

```python
frontier.add((nx, ny))
```

and one wall is required along that border edge:

```python
walls += 1
```

After discovering all regions, we choose the region threatening the most cells:

```python
if len(frontiers[i]) > len(frontiers[max_index]):
```

The quarantined region becomes:

```python
-1
```

which permanently blocks future spreading.

All remaining regions infect their frontier cells:

```python
isInfected[x][y] = 1
```

The simulation ends when no region can spread anymore.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.containVirus([
        [0, 1, 0, 0, 0, 0, 0, 1],
        [0, 1, 0, 0, 0, 0, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 0],
    ]) == 10

    assert s.containVirus([
        [1, 1, 1],
        [1, 0, 1],
        [1, 1, 1],
    ]) == 4

    assert s.containVirus([
        [1, 1, 1, 0, 0, 0, 0, 0, 0],
        [1, 0, 1, 0, 1, 1, 1, 1, 1],
        [1, 1, 1, 0, 0, 0, 0, 0, 0],
    ]) == 13

    assert s.containVirus([[0]]) == 0
    assert s.containVirus([[1]]) == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Multiple competing regions |
| Surrounded center | Exact wall counting |
| Larger simulation | Multiple rounds |
| Empty grid | No infection |
| Single infected cell | No spread possible |