Contain Virus - Leetcode Solution

The "Contain Virus" problem on LeetCode is about simulating the spread and containment of a virus in a grid-based environment. The problem statement can be summarized as follows:

You are given a grid that represents a city. Each cell in the grid can either be empty, contain a healthy person, or contain an infected person. The virus can spread from an infected person to their adjacent healthy neighbors in one time step. Once the virus has infected a healthy person, they become infected and can continue to spread the virus. You need to find the minimum number of walls that need to be built to contain the virus.

A wall can be built at any empty cell, and it takes one time step to build a wall. Once a wall is built, it separates the cells on either side, and the virus cannot spread across the wall.

To solve this problem efficiently, we need to break it down into smaller sub-problems. Here's a step-by-step approach to solving the "Contain Virus" problem on LeetCode:

Step 1: Find the initial infected regions

The first step in solving the problem is to find all the initial infected regions in the grid. An infected region is a set of cells that are infected and are connected to each other through adjacent cells. We can use a depth-first search (DFS) to find all the infected regions.

Here's the algorithm to find the infected regions:

1. Initialize an empty set to store the infected regions.

2. Initialize a 2D array of boolean values to mark the cells that we have visited.

3. For each infected cell in the grid, do the following:

   a. If the cell is not marked as visited, create a new set for the infected region.

   b. Run a DFS to find all the cells that are part of the infected region.

   c. Add the infected region to the set of infected regions.

Here's the implementation of the algorithm in Python:

def find_infected_regions(grid):
    infected_regions = set()
    visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]

    def dfs(row, col, region):
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
            return
        if grid[row][col] == 0 or visited[row][col]:
            return
        visited[row][col] = True
        region.add((row, col))
        dfs(row-1, col, region)
        dfs(row+1, col, region)
        dfs(row, col-1, region)
        dfs(row, col+1, region)

    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col] == 1 and not visited[row][col]:
                region = set()
                dfs(row, col, region)
                infected_regions.add(frozenset(region))

    return infected_regions

The function find_infected_regions takes the grid as input and returns a set of frozen sets, each of which represents an infected region.

Step 2: Find the neighboring healthy cells of infected regions

The next step is to find the neighboring healthy cells of each infected region. These are the cells that the virus can potentially spread to. We can use a breadth-first search (BFS) to find the neighboring healthy cells.

Here's the algorithm to find the neighboring healthy cells:

1. Initialize an empty set to store the neighboring healthy cells.

2. For each infected region, do the following:

   a. Initialize a queue with all the infected cells in the region.

   b. While the queue is not empty, do the following:

   i. Pop a cell from the front of the queue.

   ii. For each adjacent cell that is healthy and not marked as visited, add it to the set of neighboring healthy cells and mark it as visited.

   iii. If an adjacent cell is empty, add it to the set of candidate walls.

Here's the implementation of the algorithm in Python:

def find_neighbor_cells(grid, region):
    neighbor_cells = set()
    candidate_walls = set()
    visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]

    def bfs(queue):
        while queue:
            row, col = queue.pop(0)
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                r, c = row+dr, col+dc
                if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
                    continue
                if grid[r][c] == 0 or visited[r][c]:
                    continue
                visited[r][c] = True
                if grid[r][c] == 1:
                    neighbor_cells.add((r, c))
                    queue.append((r, c))
                else:
                    candidate_walls.add((r, c))

    for r, c in region:
        queue = [(r, c)]
        visited[r][c] = True
        bfs(queue)

    return neighbor_cells, candidate_walls

The function find_neighbor_cells takes the grid and an infected region as input and returns two sets: neighbor_cells and candidate_walls. The neighbor_cells set contains the neighboring healthy cells of the infected region, and the candidate_walls set contains the empty cells that can potentially be used to build walls.

Step 3: Find the best candidate wall

Now that we have identified the neighboring healthy cells and the candidate walls for each infected region, we need to find the best candidate wall to build. The best candidate wall is the one that separates the most number of healthy cells from the infected regions.

Here's the algorithm to find the best candidate wall:

1. Initialize a priority queue to store the candidate walls.

2. For each candidate wall, do the following:

   a. Count the number of neighboring healthy cells that it separates from all infected regions.

   b. Add the candidate wall and its corresponding score to the priority queue.

3. Pop the candidate wall with the highest score from the priority queue.

4. Build the wall at the selected cell.

5. Update the grid to reflect the new wall.

6. Update the infected regions to reflect the new wall.

Here's the implementation of the algorithm in Python:

def find_best_wall(grid, regions, walls):
    pq = []
    for wall in walls:
        score = 0
        for region in regions:
            neighbor_cells, candidate_walls = find_neighbor_cells(grid, region)
            if wall in candidate_walls:
                new_region = {(r, c) for (r, c) in region if r != wall[0] or c != wall[1]}
                new_neighbor_cells, _ = find_neighbor_cells(grid, new_region)
                score += len(new_neighbor_cells) - len(neighbor_cells)
        heapq.heappush(pq, (-score, wall))

    _, best_wall = heapq.heappop(pq)
    return best_wall

The function find_best_wall takes the grid, a set of infected regions, and a set of candidate walls as input and returns the best candidate wall to build.

Step 4: Simulate the spread and containment of the virus

The final step is to simulate the spread and containment of the virus by building walls at the selected cells until all infected cells are contained. We can keep track of the number of walls built to contain the virus and the number of time steps taken to build the walls. Once all infected cells are contained, we can return the total number of walls built to contain the virus.

Here's the algorithm to simulate the spread and containment of the virus:

1. Initialize a counter for the number of walls built and a counter for the number of time steps taken.

2. While there are infected regions in the grid, do the following:

   a. Find all infected regions in the grid.

   b. For each infected region, find the neighboring healthy cells and candidate walls.

   c. If there are no candidate walls to build, break out of the loop.

   d. Find the best candidate wall to build.

   e. Build the wall at the selected cell.

   f. Increment the wall counter.

   g. Update the grid to reflect the new wall.

   h. Update the infected regions to reflect the new wall.

   i. Increment the time step counter.

3. Return the total number of walls built to contain the virus.

Here's the implementation of the algorithm in Python:

import heapq

class Solution:
    def containVirus(self, grid: List[List[int]]) -> int:
        walls_built = 0
        time_steps = 0
        while True:
            regions = find_infected_regions(grid)
            if not regions:
                break
            for region in regions:
                neighbor_cells, candidate_walls = find_neighbor_cells(grid, region)
                if not candidate_walls:
                    continue
                wall = find_best_wall(grid, regions, candidate_walls)
                grid[wall[0]][wall[1]] = -1
                walls_built += 1
                for region in regions:
                    if wall in find_neighbor_cells(grid, region)[1]:
                        region.discard(wall)
                heapq.heapify(regions)
            time_steps += 1

        return walls_built

The containVirus function takes the grid as input and returns the total number of walls built to contain the virus. The function calls the helper functions find_infected_regions, find_neighbor_cells, and find_best_wall to find the infected regions, neighboring healthy cells, and best candidate walls, respectively. It then updates the grid and infected regions to reflect the newly-built walls and increments the wall counter and time step counter. The function terminates when there are no more infected regions in the grid and returns the total number of walls built to contain the virus.

1