Contain Virus : Deep, Intuitive & Fully Explained Guide
A virus is spreading rapidly across a grid, and your goal is to stop it by building walls around infected areas.
The grid is represented as an m x n matrix called isInfected, where each cell can either be 0 (healthy) or 1 (infected). The virus spreads every night from infected cells to their neighboring cells in all four directions up, down, left, and right unless a wall blocks the path.
You are allowed to build walls between any two adjacent cells, but only one wall can exist on the shared boundary of two cells. These walls prevent the virus from spreading across them.
However, you have limited resources. Each day, you can choose only one infected region to quarantine. A region is a continuous group of connected infected cells. Among all regions, you must pick the one that would infect the highest number of healthy cells in the next night. It is guaranteed that there will always be a clear choice with no tie.
Once you build walls around a region, it becomes fully contained and can no longer spread the virus. Meanwhile, the virus continues to spread from all other regions.
Your task is to return the total number of walls required to quarantine all the infected regions. If the virus eventually spreads to the entire grid , you should still return the total number of walls that were built until that point.
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
Explanation
Initial Observation
There are two infected regions:
- Left region → around column 1
- Right region → around column 7
We must choose the region that can infect more healthy cells next night.
Day 1 : Quarantine Most Dangerous Region
The left region threatens more cells, so we isolate it.
- Walls required = 5
- This region is now blocked completely (it will not spread anymore)
Night 1 : Virus Spreads from Remaining Region
Only the right region spreads. It infects its neighboring cells. Grid after spread becomes:
[[0,1,0,0,0,0,1,1],
[0,1,0,0,0,0,1,1],
[0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,1]]
(Left region remains unchanged because it is quarantined)
Day 2 : Quarantine Remaining Region
Now only one active region (right side) exists. Walls required to isolate it = 5
Final Result
- Day 1 walls = 5
- Day 2 walls = 5
- Total walls = 10
Example 2
Input
isInfected =
[ [1,1,1],
[1,0,1],
[1,1,1]]
Output : 4
Explanation
Initial Observation Here, almost the entire grid is infected except one cell in the center (1,1) which is still healthy (0).
All the surrounding cells (1s) form a single large infected region.
Day 1 : Choose Region to Quarantine
Since there is only one infected region, we must quarantine it. Now, observe carefully:
The infected region surrounds the center cell from all four directions. So, the virus can spread into the center cell from: Top, Bottom, Left, Right
To completely block this, we need to place walls on all 4 sides of the center cell. Walls required = 4
Night 1 : Virus Spread
Since the infected region is now fully quarantined, the virus cannot spread. The center cell remains safe.
Final Result
Only one day is needed:
- Walls built = 4
- Total walls used = 4
Step-by-Step Approach
This problem looks like a simulation, but the real trick is combining DFS + Greedy decision-making in the right way. Let’s walk through the exact approach and why each step is necessary.
Step 1: Traverse Grid & Find Regions
We scan the entire grid and run DFS (or BFS) on every unvisited infected cell (1). For each such starting point, we discover a region (a connected component of 1s). While exploring a region, we collect three important things:
- Region cells → all infected cells belonging to this region
- Frontier cells → all unique healthy (0) neighbors this region can infect
- Wall count → number of walls required to block all boundaries between this region and its frontier
Key Idea : We are not just grouping cells. we are also measuring the future threat of each region.
Step 2: Evaluate Each Region
For every region, we now know:
| Property | Meaning |
|---|---|
| Region cells | Current infected area |
| Frontier size | Number of healthy cells it can infect next |
| Wall count | Effort needed to isolate it |
Key idea: The frontier size represents the danger level of a region.
Step 3: Pick the Most Dangerous Region
We select the region with the maximum frontier size. Why this greedy choice works:
- This region will infect the maximum number of new cells in the next step
- If we don’t stop it now, it will grow rapidly and become harder to control later
- By stopping the worst region first, we minimize total future spread
This is a classic greedy strategy: Stop the biggest threat first to reduce overall damage.
Step 4: Build Walls
Add the selected region’s wall count to the final answer Mark all its cells as blocked (e.g., -1), meaning:
- This region is permanently quarantined. It will never spread again
Why marking is important: We must ensure this region is ignored in future iterations.
Step 5: Spread Virus
Now, all the remaining regions (not quarantined) will spread. For each region, convert all its frontier cells (0) → infected (1) Why this is correct:
- This simulates the
night spread - Only unblocked regions are active
- Infection grows exactly as defined in the problem
Step 6: Repeat Until No Spread Possible
We repeat the above steps until, No region has any frontier left (i.e., no more 0s to infect) or Entire grid becomes infected.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
int containVirus(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int totalWalls = 0;
while (true) {
vector<vector<pair<int,int>>> regions;
vector<unordered_set<int>> frontiers;
vector<int> walls;
vector<vector<bool>> visited(m, vector<bool>(n, false));
// Step 1: Find regions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
vector<pair<int,int>> region;
unordered_set<int> frontier;
int wallCount = 0;
dfs(grid, i, j, visited, region, frontier, wallCount);
regions.push_back(region);
frontiers.push_back(frontier);
walls.push_back(wallCount);
}
}
}
if (regions.empty()) break;
// Step 2: Find most dangerous region
int maxIdx = 0;
for (int i = 1; i < frontiers.size(); i++) {
if (frontiers[i].size() > frontiers[maxIdx].size()) {
maxIdx = i;
}
}
if (frontiers[maxIdx].empty()) break;
// Step 3: Build walls
totalWalls += walls[maxIdx];
// Step 4: Quarantine
for (auto& cell : regions[maxIdx]) {
grid[cell.first][cell.second] = -1;
}
// Step 5: Spread
for (int i = 0; i < regions.size(); i++) {
if (i == maxIdx) continue;
for (int code : frontiers[i]) {
int x = code / n;
int y = code % n;
grid[x][y] = 1;
}
}
}
return totalWalls;
}
private:
void dfs(vector<vector<int>>& grid, int i, int j,
vector<vector<bool>>& visited,
vector<pair<int,int>>& region,
unordered_set<int>& frontier,
int& wallCount) {
int m = grid.size(), n = grid[0].size();
visited[i][j] = true;
region.push_back({i,j});
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (grid[x][y] == 0) {
wallCount++;
frontier.insert(x * n + y);
} else if (grid[x][y] == 1 && !visited[x][y]) {
dfs(grid, x, y, visited, region, frontier, wallCount);
}
}
}
};
import java.util.*;
class Solution {
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int containVirus(int[][] grid) {
int m = grid.length, n = grid[0].length;
int totalWalls = 0;
while (true) {
List<List<int[]>> regions = new ArrayList<>();
List<Set<Integer>> frontiers = new ArrayList<>();
List<Integer> walls = new ArrayList<>();
boolean[][] visited = new boolean[m][n];
// Step 1: Identify all regions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
List<int[]> region = new ArrayList<>();
Set<Integer> frontier = new HashSet<>();
int[] wallCount = new int[1];
dfs(grid, i, j, visited, region, frontier, wallCount);
regions.add(region);
frontiers.add(frontier);
walls.add(wallCount[0]);
}
}
}
if (regions.isEmpty()) break;
// Step 2: Find most dangerous region
int maxIdx = 0;
for (int i = 1; i < frontiers.size(); i++) {
if (frontiers.get(i).size() > frontiers.get(maxIdx).size()) {
maxIdx = i;
}
}
// If no spread possible
if (frontiers.get(maxIdx).isEmpty()) break;
// Step 3: Build walls
totalWalls += walls.get(maxIdx);
// Step 4: Quarantine region
for (int[] cell : regions.get(maxIdx)) {
grid[cell[0]][cell[1]] = -1;
}
// Step 5: Spread virus
for (int i = 0; i < regions.size(); i++) {
if (i == maxIdx) continue;
for (int code : frontiers.get(i)) {
int x = code / n;
int y = code % n;
grid[x][y] = 1;
}
}
}
return totalWalls;
}
private void dfs(int[][] grid, int i, int j, boolean[][] visited,
List<int[]> region, Set<Integer> frontier, int[] wallCount) {
int m = grid.length, n = grid[0].length;
visited[i][j] = true;
region.add(new int[]{i, j});
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (grid[x][y] == 0) {
wallCount[0]++;
frontier.add(x * n + y);
} else if (grid[x][y] == 1 && !visited[x][y]) {
dfs(grid, x, y, visited, region, frontier, wallCount);
}
}
}
}
using System;
using System.Collections.Generic;
public class Solution {
int[][] dirs = new int[][] {
new int[]{1,0}, new int[]{-1,0},
new int[]{0,1}, new int[]{0,-1}
};
public int ContainVirus(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int totalWalls = 0;
while (true) {
var regions = new List<List<(int,int)>>();
var frontiers = new List<HashSet<int>>();
var walls = new List<int>();
bool[,] visited = new bool[m, n];
// Step 1: Find regions
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && !visited[i,j]) {
var region = new List<(int,int)>();
var frontier = new HashSet<int>();
int wallCount = 0;
DFS(grid, i, j, visited, region, frontier, ref wallCount);
regions.Add(region);
frontiers.Add(frontier);
walls.Add(wallCount);
}
}
}
if (regions.Count == 0) break;
// Step 2: Find most dangerous region
int maxIdx = 0;
for (int i = 1; i < frontiers.Count; i++) {
if (frontiers[i].Count > frontiers[maxIdx].Count) {
maxIdx = i;
}
}
if (frontiers[maxIdx].Count == 0) break;
// Step 3: Build walls
totalWalls += walls[maxIdx];
// Step 4: Quarantine
foreach (var cell in regions[maxIdx]) {
grid[cell.Item1][cell.Item2] = -1;
}
// Step 5: Spread
for (int i = 0; i < regions.Count; i++) {
if (i == maxIdx) continue;
foreach (int code in frontiers[i]) {
int x = code / n;
int y = code % n;
grid[x][y] = 1;
}
}
}
return totalWalls;
}
private void DFS(int[][] grid, int i, int j, bool[,] visited,
List<(int,int)> region, HashSet<int> frontier, ref int wallCount) {
int m = grid.Length, n = grid[0].Length;
visited[i,j] = true;
region.Add((i,j));
foreach (var d in dirs) {
int x = i + d[0], y = j + d[1];
if (x < 0 || y < 0 || x >= m || y >= n) continue;
if (grid[x][y] == 0) {
wallCount++;
frontier.Add(x * n + y);
} else if (grid[x][y] == 1 && !visited[x,y]) {
DFS(grid, x, y, visited, region, frontier, ref wallCount);
}
}
}
}
class Solution:
def containVirus(self, grid):
m, n = len(grid), len(grid[0])
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
total_walls = 0
def dfs(i, j, visited, region, frontier):
stack = [(i, j)]
visited[i][j] = True
walls = 0
while stack:
x, y = stack.pop()
region.append((x, y))
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if nx < 0 or ny < 0 or nx >= m or ny >= n:
continue
if grid[nx][ny] == 0:
walls += 1
frontier.add(nx * n + ny)
elif grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
stack.append((nx, ny))
return walls
while True:
visited = [[False]*n for _ in range(m)]
regions, frontiers, walls = [], [], []
# Step 1: Find regions
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and not visited[i][j]:
region = []
frontier = set()
wall_count = dfs(i, j, visited, region, frontier)
regions.append(region)
frontiers.append(frontier)
walls.append(wall_count)
if not regions:
break
# Step 2: Find most dangerous region
max_idx = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))
if len(frontiers[max_idx]) == 0:
break
# Step 3: Build walls
total_walls += walls[max_idx]
# Step 4: Quarantine
for x, y in regions[max_idx]:
grid[x][y] = -1
# Step 5: Spread
for i in range(len(regions)):
if i == max_idx:
continue
for code in frontiers[i]:
x, y = code // n, code % n
grid[x][y] = 1
return total_walls
Complexity Analysis
Time Complexity :O((m × n)²)
- Each iteration scans entire grid
- Multiple iterations possible (simulation)
Space Complexity : O(m × n)
Used for:
- Visited array
- Region storage
- Frontier tracking