Contain Virus
HardPrompt
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:
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:
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
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.lengthn == isInfected[i].length1 <= m, n <= 50isInfected[i][j]is either0or1.- There is always a contiguous viral region throughout the described process that will infect strictly more uncontaminated squares in the next round.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
totalWalls = 0. - Start a main loop that simulates day-by-day activity. This loop continues as long as new viruses can spread.
- Daily Analysis:
- At the beginning of each day, create a
visitedgrid 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.
- At the beginning of each day, create a
- 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.
- 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).
- Add the wall count of the most dangerous region to
- 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).
- Repeat the loop for the next day.
- Return
totalWallsafter the loop terminates.
Walkthrough
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.
Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
totalWalls = 0. - Start a
while(true)loop for the daily simulation. - Analysis and Information Gathering:
- Initialize a
visitedgrid and a list to storeRegionobjects for the current day. - Iterate through each cell
(r, c)of the grid. - If
grid[r][c] == 1and 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 thewallsNeededcount for the current region and add the neighbor's coordinates to athreatenedCellsset for the region.
- If a neighbor is an unvisited infected cell (
- After the traversal for a region is complete, store the region's properties (its cells, its
threatenedCellsset, andwallsNeeded) in the list of regions.
- Initialize a
- Termination Check: If the list of regions that threaten at least one cell is empty, break the
whileloop. - Select and Quarantine:
- Find the region in the list with the largest
threatenedCellsset size. - Add its
wallsNeededtototalWalls. - Mark all cells of this most dangerous region as quarantined (e.g., update
gridvalue to2).
- Find the region in the list with the largest
- 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
threatenedCellsset. - Update the grid by changing the value of each cell in these sets to
1(infected).
- Return
totalWallsafter the loop terminates.
Walkthrough
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.
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); } } } } }}Complexity
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).
Trade-offs
Pros
Efficient in practice by avoiding redundant computations. It reuses the
threatenedsets 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.
Solutions
Solution
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); } } } }}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); } } } }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.