LeetCode 749: Contain Virus

Problem Restatement

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

Each cell is one of:

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)

Input and Output

Example function shape:

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

Examples

Example 1

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:

10

Example 2

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:

4

Example 3

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:

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:

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:

-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:

m = number of rows
n = number of columns

The constraints are small enough for simulation.

Implementation

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:

visited = set()

For each region we store:

regions
frontiers
walls_needed

The DFS collects connected infected cells:

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

When we see an uninfected neighbor:

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

that cell becomes part of the frontier:

frontier.add((nx, ny))

and one wall is required along that border edge:

walls += 1

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

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

The quarantined region becomes:

-1

which permanently blocks future spreading.

All remaining regions infect their frontier cells:

isInfected[x][y] = 1

The simulation ends when no region can spread anymore.

Testing

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()