How do you solve Contain Virus on LeetCode?

Contain Virus (LeetCode #749) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Identifying the most threatening region is crucial for minimizing the spread of the virus.

What is the brute force solution for Contain Virus?

The brute force approach for Contain Virus is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will explore each infected region, count its perimeter, and determine how many uninfected cells it threatens. This is done by checking each cell and its neighbors iteratively. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Contain Virus?

Contain Virus uses the following concepts: Array, Depth-First Search, Breadth-First Search, Matrix, Simulation. The recommended patterns to study are: Depth-First Search (DFS), Breadth-First Search (BFS), Graph Traversal.

What are the interview tips for Contain Virus?

Clearly explain your thought process while solving the problem. Use diagrams or sketches to visualize the grid and regions if needed. Practice implementing both brute force and optimal solutions to understand the trade-offs.

What are common mistakes when solving Contain Virus?

Not properly managing visited cells can lead to infinite loops or missed regions. Failing to correctly calculate the perimeter and threats can result in incorrect wall counts.

#749

Contain Virus

Hard

ArrayDepth-First SearchBreadth-First SearchMatrixSimulationDepth-First Search (DFS)Breadth-First Search (BFS)Graph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a more structured method to efficiently identify and manage the spread of the virus, focusing on the most threatening region each time. By leveraging BFS or DFS, we can systematically track the perimeter and threats of each region.

⚙️

Algorithm

5 steps

1Step 1: Use BFS or DFS to explore each infected region and calculate its perimeter and the number of uninfected neighbors.
2Step 2: Store the regions and their respective perimeter and threat counts.
3Step 3: Identify the region that threatens the most uninfected cells and quarantine it by adding walls.
4Step 4: Spread the virus from the remaining regions to their uninfected neighbors.
5Step 5: Repeat until all regions are processed.

solution.py46 lines

1def containVirus(isInfected):
2    from collections import deque
3
4    def bfs(x, y):
5        queue = deque([(x, y)])
6        perimeter = 0
7        infected_cells = 0
8        frontier = set()
9        visited = set()
10        while queue:
11            cx, cy = queue.popleft()
12            visited.add((cx, cy))
13            infected_cells += 1
14            for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
15                nx, ny = cx + dx, cy + dy
16                if 0 <= nx < len(isInfected) and 0 <= ny < len(isInfected[0]):
17                    if isInfected[nx][ny] == 1 and (nx, ny) not in visited:
18                        queue.append((nx, ny))
19                    elif isInfected[nx][ny] == 0:
20                        frontier.add((nx, ny))
21                        perimeter += 1
22        return infected_cells, perimeter, frontier
23
24    total_walls = 0
25    while True:
26        regions = []
27        for i in range(len(isInfected)):
28            for j in range(len(isInfected[0])):
29                if isInfected[i][j] == 1:
30                    regions.append(bfs(i, j))
31        if not regions:
32            break
33        regions.sort(key=lambda x: -x[1])
34        max_region = regions[0]
35        total_walls += max_region[1]
36        for i in range(len(isInfected)):
37            for j in range(len(isInfected[0])):
38                if isInfected[i][j] == 1:
39                    isInfected[i][j] = -1
40        for nx, ny in max_region[2]:
41            isInfected[nx][ny] = 1
42        for region in regions[1:]:
43            for nx, ny in region[2]:
44                if isInfected[nx][ny] == 0:
45                    isInfected[nx][ny] = 1
46    return total_walls

ℹ

Complexity note: The optimal solution runs in O(n) time complexity due to the efficient traversal of the grid, focusing on only the relevant regions and their immediate threats.

1Identifying the most threatening region is crucial for minimizing the spread of the virus.
2Using BFS or DFS allows for efficient exploration of connected components in the grid.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.