LeetCode 749 - Contain Virus

This problem models the spread of a virus on a two-dimensional grid. Each cell is either infected (1) or uninfected (0). The virus spreads every night from infected cells to adjacent uninfected cells in the four cardinal directions: up, down, left, and right.

leetcodehardarraydepth-first-searchbreadth-first-searchmatrixsimulation

LeetCode Problem 749

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Simulation

Solution

Problem Understanding

This problem models the spread of a virus on a two-dimensional grid. Each cell is either infected (1) or uninfected (0). The virus spreads every night from infected cells to adjacent uninfected cells in the four cardinal directions: up, down, left, and right.

We are allowed to build walls to quarantine exactly one infected region per day. A region is a connected component of infected cells using 4-directional connectivity. Once a region is quarantined, it can no longer spread the virus.

The important restriction is that we must choose the region that would infect the largest number of currently uninfected cells during the next spread phase. The problem guarantees there is never a tie, so the choice is always unique.

The task is to compute the total number of walls built until the virus is fully contained or the entire grid becomes infected.

The input is an m x n matrix where:

  • 0 means uninfected
  • 1 means infected and active
  • During the simulation we will also typically introduce a third value internally, such as -1, to mark quarantined regions

The output is a single integer representing the total number of walls constructed throughout the process.

The constraints are relatively small:

  • 1 <= m, n <= 50
  • Maximum grid size is 2500 cells

This allows us to repeatedly scan the entire grid and perform graph traversals such as DFS or BFS without performance issues.

Several edge cases are important:

  • A region may already be fully surrounded and unable to spread
  • Multiple infected regions may exist simultaneously
  • The entire grid may already be infected
  • A single infected cell may require multiple walls depending on neighboring uninfected cells
  • After one region is quarantined, all remaining regions spread simultaneously

A naive implementation can easily make mistakes by allowing quarantined regions to spread again, double-counting walls, or updating the grid in the wrong order.

Approaches

Brute Force Approach

A brute force approach would attempt to simulate every possible quarantine choice each day. For every infected region, we could:

  1. Simulate quarantining that region
  2. Simulate virus spread for all others
  3. Compare resulting states
  4. Pick the best choice

This works because it explicitly evaluates every possible action and chooses the optimal one according to the problem rules.

However, this is unnecessarily expensive because the problem already tells us how to choose the region: quarantine the one threatening the largest number of uninfected cells. We do not need to simulate all possibilities independently.

The brute force solution repeatedly copies grids and performs many redundant spread simulations, making it much slower than necessary.

Optimal Approach

The key observation is that for each connected infected region, we only need three pieces of information:

  1. The cells belonging to the region
  2. The set of uninfected cells the region could infect next
  3. The number of walls required to isolate the region

Once we compute this information for every region:

  • We quarantine the region threatening the largest number of cells
  • We add its wall count to the answer
  • We mark that region as permanently blocked
  • All other regions spread simultaneously

This naturally leads to a repeated DFS or BFS simulation.

The grid size is small enough that rescanning the board each round is completely feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)^3) O(mn) Simulates many redundant future states
Optimal O((mn)^2) O(mn) Repeated DFS/BFS with direct region analysis

Algorithm Walkthrough

  1. Initialize the total wall count to zero.
  2. Repeatedly process the grid until no active region can spread further.
  3. During each iteration, scan the grid and identify all connected infected regions using DFS or BFS.
  4. For every region, maintain:
  • A list of infected cells in the region
  • A set of neighboring uninfected cells that could be infected next
  • The number of walls required to isolate the region
  1. While exploring a region:

  • If we encounter an adjacent uninfected cell, we:

  • Add it to the threatened set

  • Increase the wall count by one

  • If we encounter another infected cell, continue traversal

  1. After processing all regions, determine which region threatens the largest number of uninfected cells.
  2. If no region can spread anymore, terminate the simulation and return the accumulated wall count.
  3. Add the chosen region's wall count to the answer.
  4. Mark all cells in the quarantined region using a special value such as -1. This prevents them from spreading in future rounds.
  5. For every other active region:
  • Infect all threatened neighboring cells
  • This spread happens simultaneously for all non-quarantined regions
  1. Repeat the process until containment is complete.

Why it works

At every step, the algorithm exactly follows the problem's rules. Each connected component is independently analyzed to determine how many cells it threatens and how many walls are needed. The region threatening the most cells is quarantined, while all others spread simultaneously. Because quarantined regions are permanently marked and excluded from future spreads, the simulation remains faithful to the intended process. Repeating this procedure eventually reaches a stable state where no active region can infect additional cells.

Python Solution

from typing import List, Set, Tuple

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 and (r, c) not in visited:
                        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 0 <= nx < rows and 0 <= ny < cols:
                                    if isInfected[nx][ny] == 1 and (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

            quarantine_index = 0

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

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

            total_walls += walls_needed[quarantine_index]

            # Quarantine selected region
            for x, y in regions[quarantine_index]:
                isInfected[x][y] = -1

            # Spread remaining regions
            for i in range(len(regions)):
                if i == quarantine_index:
                    continue

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

        return total_walls

The implementation repeatedly performs region discovery and simulation rounds.

The visited set prevents processing the same infected cell multiple times during DFS. Each DFS traversal collects all cells belonging to one connected infected region.

For every region, three structures are maintained:

  • region, the infected cells belonging to the component
  • frontier, the uninfected cells reachable next round
  • walls, the exact number of walls required

Whenever DFS sees an adjacent uninfected cell, it increments the wall count. Multiple infected cells touching the same uninfected cell contribute multiple walls, which matches the problem statement.

After all regions are analyzed, the algorithm selects the region with the largest frontier. That region is quarantined by marking its cells as -1.

All remaining regions then infect their frontier cells simultaneously.

The process repeats until no region can spread further.

Go Solution

package main

func containVirus(isInfected [][]int) int {
	rows := len(isInfected)
	cols := len(isInfected[0])

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	totalWalls := 0

	for {
		visited := make(map[[2]int]bool)

		var regions [][][]int
		var frontiers []map[[2]int]bool
		var wallsNeeded []int

		for r := 0; r < rows; r++ {
			for c := 0; c < cols; c++ {
				key := [2]int{r, c}

				if isInfected[r][c] == 1 && !visited[key] {
					stack := [][]int{{r, c}}

					visited[key] = true

					var region [][]int
					frontier := make(map[[2]int]bool)

					walls := 0

					for len(stack) > 0 {
						cell := stack[len(stack)-1]
						stack = stack[:len(stack)-1]

						x, y := cell[0], cell[1]

						region = append(region, []int{x, y})

						for _, d := range directions {
							nx := x + d[0]
							ny := y + d[1]

							if nx >= 0 && nx < rows && ny >= 0 && ny < cols {
								nextKey := [2]int{nx, ny}

								if isInfected[nx][ny] == 1 && !visited[nextKey] {
									visited[nextKey] = true
									stack = append(stack, []int{nx, ny})
								} else if isInfected[nx][ny] == 0 {
									frontier[nextKey] = true
									walls++
								}
							}
						}
					}

					regions = append(regions, region)
					frontiers = append(frontiers, frontier)
					wallsNeeded = append(wallsNeeded, walls)
				}
			}
		}

		if len(frontiers) == 0 {
			break
		}

		quarantineIndex := 0

		for i := 1; i < len(frontiers); i++ {
			if len(frontiers[i]) > len(frontiers[quarantineIndex]) {
				quarantineIndex = i
			}
		}

		if len(frontiers[quarantineIndex]) == 0 {
			break
		}

		totalWalls += wallsNeeded[quarantineIndex]

		for _, cell := range regions[quarantineIndex] {
			x, y := cell[0], cell[1]
			isInfected[x][y] = -1
		}

		for i := 0; i < len(regions); i++ {
			if i == quarantineIndex {
				continue
			}

			for pos := range frontiers[i] {
				x, y := pos[0], pos[1]
				isInfected[x][y] = 1
			}
		}
	}

	return totalWalls
}

The Go implementation follows the same overall logic as the Python version. Since Go does not have built-in tuple types or sets, maps with fixed-size array keys are used for visited tracking and frontier storage.

Slices are used for DFS stacks and region storage. Integer overflow is not a concern because the grid contains at most 2500 cells, and the wall count remains well within Go's int range.

Worked Examples

Example 1

Input:

[
  [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]
]

Day 1 Region Analysis

Region Cells Threatened Cells Walls Needed
Left region {(0,1),(1,1)} 5 cells 5
Right region {(0,7),(1,7),(2,7)} 4 cells 4

The left region threatens more cells, so it is quarantined.

Walls added: 5

Grid after quarantine and spread:

[
  [0,-1,0,0,0,0,1,-1],
  [0,-1,0,0,0,0,1,-1],
  [0,0,0,0,0,0,1,-1],
  [0,0,0,0,0,0,0,1]
]

Day 2 Region Analysis

Region Threatened Cells Walls Needed
Remaining right region 5 cells 5

Quarantine this region.

Walls added: 5

Total walls:

5 + 5 = 10

Example 2

Input:

[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

Only one region exists.

The center cell is threatened from all four directions.

Threatened Cell Number of Required Walls
(1,1) 4

The algorithm correctly counts four walls because every shared boundary needs its own wall.

Final answer:

4

Example 3

Input:

[
  [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]
]

Initial Regions

Region Threatened Cells Walls Needed
Left block 2 2
Right block 6 11

The right region threatens more cells, so it is quarantined first.

After spread, the left region expands slightly.

Second iteration requires two more walls.

Total:

11 + 2 = 13

Complexity Analysis

Measure Complexity Explanation
Time O((mn)^2) Each simulation round scans the grid and there can be at most O(mn) rounds
Space O(mn) DFS structures, visited set, and frontier sets

The algorithm repeatedly scans the entire grid to discover connected regions and simulate virus spread. Each round processes at most all cells in the grid. In the worst case, the number of rounds is also bounded by the number of cells, giving a total complexity of O((mn)^2).

The auxiliary memory comes from storing visited cells, DFS stacks, region lists, and frontier sets.

Test Cases

from typing import List

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 and (r, c) not in visited:
                        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 0 <= nx < rows and 0 <= ny < cols:
                                    if isInfected[nx][ny] == 1 and (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

            quarantine_index = 0

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

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

            total_walls += walls_needed[quarantine_index]

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

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

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

        return total_walls

sol = Solution()

# Example 1
assert sol.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  # multiple regions with sequential containment

# Example 2
assert sol.containVirus([
    [1,1,1],
    [1,0,1],
    [1,1,1]
]) == 4  # one surrounded cell requiring four walls

# Example 3
assert sol.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  # complex multi-round spread

# Single infected cell
assert sol.containVirus([
    [1]
]) == 0  # no uninfected neighbors

# Single infected cell with neighbors
assert sol.containVirus([
    [1,0]
]) == 1  # one wall needed

# Already fully infected
assert sol.containVirus([
    [1,1],
    [1,1]
]) == 0  # no spread possible

# No infection
assert sol.containVirus([
    [0,0],
    [0,0]
]) == 0  # nothing to contain

# Two isolated infections
assert sol.containVirus([
    [1,0,1]
]) == 1  # one region quarantined, other spreads

# Vertical line infection
assert sol.containVirus([
    [1],
    [0],
    [0]
]) == 1  # single downward spread

# Region touching same frontier multiple times
assert sol.containVirus([
    [1,1],
    [1,0]
]) == 2  # same cell requires multiple walls
Test Why
Example 1 Verifies multiple containment rounds
Example 2 Verifies multiple walls for one frontier cell
Example 3 Verifies complex spread dynamics
Single infected cell Verifies no walls when no spread possible
Single infected cell with neighbor Verifies minimal wall construction
Already fully infected Verifies stable terminal state
No infection Verifies empty simulation
Two isolated infections Verifies independent region processing
Vertical line infection Verifies boundary handling
Shared frontier case Verifies correct wall counting

Edge Cases

One important edge case occurs when the grid is already fully infected. In this situation, there are no uninfected cells remaining, so no region can spread further. A buggy implementation might still attempt to build walls unnecessarily. The solution handles this correctly because every region's frontier becomes empty, causing the simulation loop to terminate immediately.

Another tricky case is when multiple infected cells border the same uninfected cell. A naive implementation might count only one wall because the frontier set stores unique cells. However, the problem requires counting walls per shared boundary, not per frontier cell. The implementation correctly increments the wall count every time an infected-to-uninfected edge is encountered.

A third subtle case is simultaneous spread. After quarantining one region, all remaining regions spread at the same time. If the implementation updates one region and then processes another sequentially using the modified grid, the result becomes incorrect. The solution avoids this by first computing all frontiers before performing any spread updates.

A final edge case involves quarantined regions. Once isolated, they must never spread again. Forgetting to distinguish quarantined cells from active infected cells causes repeated spreading and infinite loops. Marking quarantined cells as -1 cleanly separates them from active infection states.