We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Contain Virus

Number: 750

Difficulty: Hard

Paid? No

Companies: Bloomberg

Problem Description

We are given an m x n grid where a cell value of 1 indicates an infected region while a 0 represents an uninfected cell. Each day, the virus can spread from any infected cell to its neighboring cells (only in the up, down, left, and right directions), unless prevented by a wall. However, you have the ability to build walls around one particular infected region per day—the region that would infect the most uninfected cells if left unchecked. When you build walls around that region, its cells are quarantined and will not spread infection further. Meanwhile, the other regions are allowed to spread. The process repeats until no infected region can further infect uninfected cells. The goal is to determine the total number of walls built to quarantine the virus.

Key Insights

  • Use a graph traversal (BFS/DFS) to identify each connected region of infection.
  • For each region, compute:
    • The set of neighboring uninfected cells that are under threat.
    • The number of walls required to quarantine that region.
  • Choose the region with the highest number of adjacent uninfected cells (i.e. highest threat) to quarantine first.
  • After quarantining one region, let the other regions spread and repeat the process until the virus cannot spread further.
  • Marking quarantined cells (for example, with -1) prevents them from being reprocessed.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)) in the worst case, due to repeated full scans and region traversals. Space Complexity: O(m * n), which is used for auxiliary data structures like visited arrays and frontier sets.

Solution

The solution uses simulation with multiple iterations (one per day) to contain the virus. In each iteration:

  1. Traverse the grid using BFS/DFS to capture all connected infected regions.
  2. For every region, compute its frontier (adjacent uninfected cells) and the number of walls needed.
  3. Determine the most dangerous region (largest frontier) and quarantine it by marking its cells so they stop spreading.
  4. Update the grid by allowing all other regions to infect their frontier cells.
  5. Accumulate the total number of walls built. Data structures such as queues (for BFS), sets (for unique frontier cells), and boolean arrays (for visited status) are utilized to accurately simulate this daily process.

Code Solutions

# Python Solution
from collections import deque

def containVirus(isInfected):
    m, n = len(isInfected), len(isInfected[0])
    result = 0
    
    def neighbors(i, j):
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= x < m and 0 <= y < n:
                yield x, y

    while True:
        regions = []      # list of infected regions (each region is a list of cells)
        frontiers = []    # corresponding list of frontiers (adjacent uninfected cells)
        walls_needed = [] # number of walls needed for each region
        visited = [[False] * n for _ in range(m)]
        
        # Identify all regions using BFS.
        for i in range(m):
            for j in range(n):
                if isInfected[i][j] == 1 and not visited[i][j]:
                    region = []
                    frontier = set()
                    walls = 0
                    queue = deque([(i, j)])
                    visited[i][j] = True
                    while queue:
                        ci, cj = queue.popleft()
                        region.append((ci, cj))
                        for ni, nj in neighbors(ci, cj):
                            if isInfected[ni][nj] == 0:
                                walls += 1
                                frontier.add((ni, nj))
                            elif isInfected[ni][nj] == 1 and not visited[ni][nj]:
                                visited[ni][nj] = True
                                queue.append((ni, nj))
                    regions.append(region)
                    frontiers.append(frontier)
                    walls_needed.append(walls)
        
        if not regions:
            break

        # Select region with maximum threat (largest frontier)
        idx = 0
        for i in range(1, len(frontiers)):
            if len(frontiers[i]) > len(frontiers[idx]):
                idx = i

        # If no region can spread, we are done.
        if len(frontiers[idx]) == 0:
            break

        result += walls_needed[idx]

        # Quarantine the chosen region by marking cells.
        for i, j in regions[idx]:
            isInfected[i][j] = -1

        # Spread virus from all other regions.
        for k in range(len(regions)):
            if k == idx:
                continue
            for i, j in frontiers[k]:
                if isInfected[i][j] == 0:
                    isInfected[i][j] = 1

    return result

# Example usage:
print(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]]))
← Back to All Questions