#749

Hard

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Contain Virus

Contain Virus involves using array-based Depth-First Search to contain viral spread by building walls around infected regions.

array depth first search breadth first search matrix simulation

Problem Statement

You are tasked with containing a rapidly spreading virus. The world is represented as an m x n grid, where isInfected[i][j] == 1 indicates an infected cell and isInfected[i][j] == 0 represents an uninfected cell. Every day, the virus spreads to all four directions unless blocked by walls. Your goal is to quarantine the infected regions by building walls between the most threatening viral regions and the uninfected cells. Walls can only be placed on the shared boundaries between adjacent cells.

Each day, you are allowed to build walls around one infected region that will threaten the most uninfected cells the following night. The region that poses the greatest risk of spreading to nearby cells must be contained first. The virus continues to spread, and the goal is to completely isolate all infected regions by adding walls at each step. The task is to determine how many walls are necessary to fully contain the virus.

Examples

Example 1

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

Output: 10

There are 2 contaminated regions. On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2

Input: isInfected = [[1,1,1],[1,0,1],[1,1,1]]

Output: 4

Even though there is only one cell saved, there are 4 walls built. Notice that walls are only built on the shared boundary of two different cells.

Example 3

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

Output: 13

The region on the left only builds two new walls.

Constraints

m == isInfected.length
n == isInfected[i].length
1 <= m, n <= 50
isInfected[i][j] is either 0 or 1.
There is always a contiguous viral region throughout the described process that will infect strictly more uncontaminated squares in the next round.

Solution Approach

Identify and Track Viral Regions

Use Depth-First Search (DFS) to find all infected regions. These regions are contiguous blocks of infected cells, and tracking them will allow for targeted wall placement. DFS will help mark boundaries of each infected region to prepare for wall construction.

Assess the Spread Potential

For each viral region, calculate the number of uninfected cells adjacent to it. This will determine the potential spread if the region is not contained. The goal is to isolate the region that will infect the most cells in the next round, minimizing future infections.

Construct Walls Around the Most Threatening Region

Once the most dangerous region is identified, place walls along the boundary to contain it. This reduces the virus's ability to spread in the next round. Repeat the process for each subsequent day until all viral regions are contained.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the DFS traversal, which can go through all the cells in the grid. Given the grid size of m x n, the time complexity is O(m * n). The space complexity is also O(m * n) due to the recursive stack of DFS and the need to store the visited cells.

What Interviewers Usually Probe

Candidate demonstrates a strong understanding of DFS and its application to this problem.
The ability to identify and prioritize the most threatening viral regions indicates an efficient solution approach.
Clear understanding of how to simulate the virus spread and use walls to contain it will be crucial.

Common Pitfalls or Variants

Common pitfalls

Failing to track the boundaries of infected regions properly can lead to incorrect wall placement.
Not correctly assessing which viral region will spread the most can result in inefficient containment.
Over-complicating the algorithm without optimizing the DFS can lead to performance issues on larger grids.

Follow-up variants

Consider adding additional constraints, such as limiting the number of walls that can be placed.
Modify the problem to allow walls to be built in multiple regions simultaneously.
Implement the solution using a Breadth-First Search (BFS) approach instead of DFS to compare performance and efficiency.

FAQ

How does DFS help solve the Contain Virus problem?

DFS helps by traversing each infected region to track its boundaries and identify the cells that need to be blocked to prevent further virus spread.

What strategy should I use to prioritize which infected region to quarantine first?

You should prioritize the region that will infect the most uninfected cells in the next round, as this will minimize the total number of infections.

What happens if I don't place walls around the most threatening viral region?

If you don't quarantine the most threatening region first, the virus will spread more rapidly, requiring more walls and increasing the overall number of walls needed.

Can I use BFS instead of DFS for this problem?

Yes, you can use BFS to solve the problem, though it may lead to different performance characteristics. Both DFS and BFS are valid, but DFS is often more intuitive for this type of problem.

What are the key challenges when solving Contain Virus?

The main challenges include correctly identifying the viral regions, efficiently calculating the spread potential, and ensuring the walls are placed in the optimal locations.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def containVirus(self, isInfected: List[List[int]]) -> int:
        def dfs(i, j):
            vis[i][j] = True
            areas[-1].append((i, j))
            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n:
                    if isInfected[x][y] == 1 and not vis[x][y]:
                        dfs(x, y)
                    elif isInfected[x][y] == 0:
                        c[-1] += 1
                        boundaries[-1].add((x, y))

        m, n = len(isInfected), len(isInfected[0])
        ans = 0
        while 1:
            vis = [[False] * n for _ in range(m)]
            areas = []
            c = []
            boundaries = []
            for i, row in enumerate(isInfected):
                for j, v in enumerate(row):
                    if v == 1 and not vis[i][j]:
                        areas.append([])
                        boundaries.append(set())
                        c.append(0)
                        dfs(i, j)
            if not areas:
                break
            idx = boundaries.index(max(boundaries, key=len))
            ans += c[idx]
            for k, area in enumerate(areas):
                if k == idx:
                    for i, j in area:
                        isInfected[i][j] = -1
                else:
                    for i, j in area:
                        for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                            x, y = i + a, j + b
                            if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:
                                isInfected[x][y] = 1
        return ans

Continue Practicing

#733 flood fill #778 swim in rising water #695 max area of island