# Contain Virus
**Difficulty:** HARD
[External](https://leetcode.com/problems/contain-virus)
Canonical: https://scaleengineer.com/dsa/problems/contain-virus
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## Problem
A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as an `m x n` binary grid `isInfected`, where `isInfected[i][j] == 0` represents uninfected cells, and `isInfected[i][j] == 1` represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two **4-directionally** adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region (i.e., the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night). There **will never be a tie**.

Return _the number of walls used to quarantine all the infected regions_. If the world will become fully infected, return the number of walls used.

**Example 1:**

![](https://assets.glich.co/dsa/contain-virus/image0.jpg) 

**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
**Explanation:** 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:
![](https://assets.glich.co/dsa/contain-virus/image1.jpg)
On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.
![](https://assets.glich.co/dsa/contain-virus/image2.jpg)

**Example 2:**

![](https://assets.glich.co/dsa/contain-virus/image3.jpg) 

**Input:** isInfected = [[1,1,1],[1,0,1],[1,1,1]]
**Output:** 4
**Explanation:** 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
**Explanation:** 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.

# Approaches
## Simulation with Redundant Spreading Phase
This approach directly simulates the day-by-day process described in the problem. In each iteration, it first performs an analysis phase to find all distinct viral regions and their properties. After choosing the most threatening region to quarantine, it enters a spreading phase. The inefficiency in this version comes from the spreading phase, where it re-scans the entire grid to find which uninfected cells are adjacent to the remaining viral regions, even though this information was available from the initial analysis.
**Time:** O((M * N)^2). Each day's simulation takes O(M * N) time. The analysis phase involves a traversal over the grid, which is O(M * N). The redundant spreading phase also takes O(M * N). In the worst case, the simulation can run for O(M * N) days, leading to the total complexity. · **Space:** O(M * N), where M and N are the dimensions of the grid. This is for storing the `visited` grid, the BFS/DFS queue, and the properties of each region, including the sets of infected and threatened cells.
**Pros:** The logic is straightforward, with a clear separation between the analysis, quarantine, and spreading phases.; It correctly models the described scenario and provides the correct answer.
**Cons:** This approach is less efficient because it re-computes information. The set of threatened cells for all regions is already determined during the analysis phase. This approach discards that information for the non-quarantined regions and then performs another full grid scan to re-calculate which cells will be infected.
### Explanation
The simulation proceeds in a loop, where each cycle represents one day. 

First, we identify all separate regions of infected cells (value `1`) that haven't been quarantined yet. We can do this by iterating through the grid and starting a Breadth-First Search (BFS) or Depth-First Search (DFS) whenever we find an unvisited infected cell. During this traversal, we calculate for each region: the number of walls needed to enclose it and the count of unique uninfected cells it would spread to. 

Once all regions are analyzed, we select the one that threatens the most cells. We add its wall count to our total and update the grid to mark this region as permanently quarantined (e.g., by setting its cell values to `2`).

Next, to simulate the spread of the remaining viruses, this approach performs a new, full scan of the grid. It identifies all remaining infected cells (value `1`) and finds all their adjacent uninfected neighbors (value `0`). These neighbors are then marked for infection. This step is redundant because the neighbors for each region were already identified during the analysis phase. The process repeats until no more cells can be infected.
### Algorithm
1.  Initialize `totalWalls = 0`.
2.  Start a main loop that simulates day-by-day activity. This loop continues as long as new viruses can spread.
3.  **Daily Analysis:**
    *   At the beginning of each day, create a `visited` grid to track cells analyzed during this day's traversals.
    *   Iterate through the entire grid to find the start of each un-quarantined viral region (cells with value `1`).
    *   For each region found, perform a traversal (like BFS or DFS) to identify all its cells, the number of walls needed to contain it, and the set of uninfected cells it threatens.
    *   Store these properties for each region.
4.  **Select Region to Quarantine:**
    *   After analyzing all regions, identify the one that threatens the most uninfected cells. The problem guarantees no ties.
    *   If no regions threaten any cells, the simulation is over. Break the main loop.
5.  **Quarantine:**
    *   Add the wall count of the most dangerous region to `totalWalls`.
    *   Update the grid by marking all cells of this region as quarantined (e.g., changing their value to `2`).
6.  **Virus Spread (Redundant Step):**
    *   Create a temporary set to store coordinates of cells that will become newly infected.
    *   Iterate through the entire grid again. For every cell that is currently infected (value `1`), check its four neighbors.
    *   If a neighbor is uninfected (value `0`), add its coordinates to the temporary set.
    *   After the scan is complete, iterate through the temporary set and update the grid, changing the state of these cells to infected (value `1`).
7.  Repeat the loop for the next day.
8.  Return `totalWalls` after the loop terminates.

## Optimized Simulation by Reusing Information
This approach is an optimized version of the direct simulation. It also follows a day-by-day simulation but avoids redundant work by intelligently reusing information. During the initial analysis phase of each day, it gathers all necessary information: which cells belong to which region, how many walls are needed for each, and which uninfected cells each region threatens. This information is then used for both selecting the region to quarantine and for spreading the virus from all other regions, eliminating the need for a second, costly grid scan.
**Time:** O((M * N)^2). Each day's simulation is a single efficient O(M * N) operation. This involves finding all regions and their properties. The number of days, D, can be at most O(M * N). Thus, the total time complexity is O(D * M * N) = O((M * N)^2). This is efficient enough for the given constraints (M, N <= 50). · **Space:** O(M * N). Space is required for the `visited` grid, the recursion stack or queue for traversal, and to store the data for all regions. In the worst case, the total number of cells stored across all regions is O(M * N).
**Pros:** Efficient in practice by avoiding redundant computations. It reuses the `threatened` sets calculated during the analysis phase for the spreading phase.; It's a direct and robust simulation of the problem that is guaranteed to be correct.; Good software engineering practice by following the Don't Repeat Yourself (DRY) principle.
**Cons:** The asymptotic time complexity remains O((M*N)^2), which could be slow for significantly larger grids than specified in the constraints.
### Explanation
This method refines the simulation by being more efficient with the data it gathers. The simulation loop runs day by day.

At the start of each day, we perform a single pass to identify all current viral regions. Using a traversal algorithm like BFS, we find each connected component of infected cells (`1`). For each region, we build a comprehensive profile: a set of its constituent cells, a set of the unique uninfected cells it threatens, and the total number of walls required for containment. All these profiles are stored.

With all regions analyzed, we pick the most dangerous one (based on the size of its threatened cells set), add its wall count to the total, and update its cells on the grid to a 'quarantined' state (`2`).

The key optimization is in the spreading phase. Instead of re-scanning the grid, we simply iterate through the region profiles we've already built. For every region *except* the one we just quarantined, we take its pre-computed set of threatened cells and update them on the grid to become infected (`1`). This reuse of data makes each day's simulation faster and cleaner.

The simulation stops when no regions pose a threat to any uninfected cells.

```java
class Solution {
    // Helper class to store properties of a viral region
    class Region {
        // Using r * n + c to uniquely identify cells in a Set
        Set<Integer> infected = new HashSet<>();
        Set<Integer> threatened = new HashSet<>();
        int walls = 0;
    }

    public int containVirus(int[][] isInfected) {
        int m = isInfected.length;
        int n = isInfected[0].length;
        int totalWalls = 0;

        while (true) {
            List<Region> regions = new ArrayList<>();
            boolean[][] visited = new boolean[m][n];

            // 1. Find all regions and their properties for the current day
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] == 1 && !visited[i][j]) {
                        Region region = new Region();
                        findRegion(i, j, m, n, isInfected, visited, region);
                        if (!region.threatened.isEmpty()) {
                            regions.add(region);
                        }
                    }
                }
            }

            // 2. If no regions can spread, the process is over
            if (regions.isEmpty()) {
                break;
            }

            // 3. Find the most dangerous region
            regions.sort((a, b) -> b.threatened.size() - a.threatened.size());
            Region mostDangerous = regions.get(0);

            // 4. Add walls and quarantine the most dangerous region
            totalWalls += mostDangerous.walls;
            for (int cellCode : mostDangerous.infected) {
                int r = cellCode / n;
                int c = cellCode % n;
                isInfected[r][c] = 2; // 2 = quarantined
            }

            // 5. Spread the virus from all other regions
            for (int i = 1; i < regions.size(); i++) {
                for (int cellCode : regions.get(i).threatened) {
                    int r = cellCode / n;
                    int c = cellCode % n;
                    isInfected[r][c] = 1; // 1 = infected
                }
            }
        }
        return totalWalls;
    }

    private void findRegion(int startR, int startC, int m, int n, int[][] grid, boolean[][] visited, Region region) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startR, startC});
        visited[startR][startC] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1];
            region.infected.add(r * n + c);

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if (grid[nr][nc] == 1 && !visited[nr][nc]) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    } else if (grid[nr][nc] == 0) {
                        region.walls++;
                        region.threatened.add(nr * n + nc);
                    }
                }
            }
        }
    }
}
```
### Algorithm
1.  Initialize `totalWalls = 0`.
2.  Start a `while(true)` loop for the daily simulation.
3.  **Analysis and Information Gathering:**
    *   Initialize a `visited` grid and a list to store `Region` objects for the current day.
    *   Iterate through each cell `(r, c)` of the grid.
    *   If `grid[r][c] == 1` and it has not been visited, start a traversal (BFS is a good choice) to find one complete viral region.
    *   During the traversal, for each infected cell, check its 4-directional neighbors:
        *   If a neighbor is an unvisited infected cell (`1`), add it to the traversal queue.
        *   If a neighbor is an uninfected cell (`0`), increment the `wallsNeeded` count for the current region and add the neighbor's coordinates to a `threatenedCells` set for the region.
    *   After the traversal for a region is complete, store the region's properties (its cells, its `threatenedCells` set, and `wallsNeeded`) in the list of regions.
4.  **Termination Check:** If the list of regions that threaten at least one cell is empty, break the `while` loop.
5.  **Select and Quarantine:**
    *   Find the region in the list with the largest `threatenedCells` set size.
    *   Add its `wallsNeeded` to `totalWalls`.
    *   Mark all cells of this most dangerous region as quarantined (e.g., update `grid` value to `2`).
6.  **Optimized Virus Spread:**
    *   Iterate through the list of regions found in the analysis step.
    *   For every region that was **not** the one just quarantined, access its stored `threatenedCells` set.
    *   Update the grid by changing the value of each cell in these sets to `1` (infected).
7.  Return `totalWalls` after the loop terminates.

# Solutions
### Java

```java
class Solution {
private
  static final int[] DIRS = {-1, 0, 1, 0, -1};
private
  List<Integer> c = new ArrayList<>();
private
  List<List<Integer>> areas = new ArrayList<>();
private
  List<Set<Integer>> boundaries = new ArrayList<>();
private
  int[][] infected;
private
  boolean[][] vis;
private
  int m;
private
  int n;
public
  int containVirus(int[][] isInfected) {
    infected = isInfected;
    m = infected.length;
    n = infected[0].length;
    vis = new boolean[m][n];
    int ans = 0;
    while (true) {
      for (boolean[] row : vis) {
        Arrays.fill(row, false);
      }
      c.clear();
      areas.clear();
      boundaries.clear();
      for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
          if (infected[i][j] == 1 && !vis[i][j]) {
            c.add(0);
            areas.add(new ArrayList<>());
            boundaries.add(new HashSet<>());
            dfs(i, j);
          }
        }
      }
      if (areas.isEmpty()) {
        break;
      }
      int idx = max(boundaries);
      ans += c.get(idx);
      for (int t = 0; t < areas.size(); ++t) {
        if (t == idx) {
          for (int v : areas.get(t)) {
            int i = v / n, j = v % n;
            infected[i][j] = -1;
          }
        } else {
          for (int v : areas.get(t)) {
            int i = v / n, j = v % n;
            for (int k = 0; k < 4; ++k) {
              int x = i + DIRS[k], y = j + DIRS[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && infected[x][y] == 0) {
                infected[x][y] = 1;
              }
            }
          }
        }
      }
    }
    return ans;
  }
private
  int max(List<Set<Integer>> boundaries) {
    int idx = 0;
    int mx = boundaries.get(0).size();
    for (int i = 1; i < boundaries.size(); ++i) {
      int t = boundaries.get(i).size();
      if (mx < t) {
        mx = t;
        idx = i;
      }
    }
    return idx;
  }
private
  void dfs(int i, int j) {
    vis[i][j] = true;
    int idx = areas.size() - 1;
    areas.get(idx).add(i * n + j);
    for (int k = 0; k < 4; ++k) {
      int x = i + DIRS[k], y = j + DIRS[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (infected[x][y] == 1 && !vis[x][y]) {
          dfs(x, y);
        } else if (infected[x][y] == 0) {
          c.set(idx, c.get(idx) + 1);
          boundaries.get(idx).add(x * n + y);
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  const vector<int> dirs = {-1, 0, 1, 0, -1};
  vector<int> c;
  vector<vector<int>> areas;
  vector<unordered_set<int>> boundaries;
  vector<vector<int>> infected;
  vector<vector<bool>> vis;
  int m;
  int n;
  int containVirus(vector<vector<int>> &isInfected) {
    infected = isInfected;
    m = infected.size();
    n = infected[0].size();
    vis.assign(m, vector<bool>(n));
    int ans = 0;
    while (1) {
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          vis[i][j] = false;
      c.clear();
      areas.clear();
      boundaries.clear();
      for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
          if (infected[i][j] == 1 && !vis[i][j]) {
            c.push_back(0);
            areas.push_back({});
            boundaries.push_back({});
            dfs(i, j);
          }
        }
      }
      if (areas.empty())
        break;
      int idx = getMax();
      ans += c[idx];
      for (int t = 0; t < areas.size(); ++t) {
        if (t == idx) {
          for (int v : areas[t]) {
            int i = v / n, j = v % n;
            infected[i][j] = -1;
          }
        } else {
          for (int v : areas[t]) {
            int i = v / n, j = v % n;
            for (int k = 0; k < 4; ++k) {
              int x = i + dirs[k], y = j + dirs[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && infected[x][y] == 0)
                infected[x][y] = 1;
            }
          }
        }
      }
    }
    return ans;
  }
  int getMax() {
    int idx = 0;
    int mx = boundaries[0].size();
    for (int i = 1; i < boundaries.size(); ++i) {
      int t = boundaries[i].size();
      if (mx < t) {
        mx = t;
        idx = i;
      }
    }
    return idx;
  }
  void dfs(int i, int j) {
    vis[i][j] = true;
    areas.back().push_back(i * n + j);
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (infected[x][y] == 1 && !vis[x][y])
          dfs(x, y);
        else if (infected[x][y] == 0) {
          c.back() += 1;
          boundaries.back().insert(x * n + y);
        }
      }
    }
  }
};

```

### Python

```python
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

```