Facebook Pixel

749. Contain Virus

HardDepth-First SearchBreadth-First SearchArrayMatrixSimulation
Leetcode Link

Problem Description

You're given an m x n grid representing a world where a virus is spreading. In this grid:

  • isInfected[i][j] == 0 means the cell is uninfected (healthy)
  • isInfected[i][j] == 1 means the cell is infected with the virus

The virus spreads each night to all 4-directionally adjacent cells (up, down, left, right) unless blocked by a wall. You can install walls between any two adjacent cells on their shared boundary.

Each day, you have limited resources and can only build walls around one infected region (a continuous block of connected infected cells). You must choose the region that threatens the most uninfected cells for the next night's spread. The problem guarantees there will never be a tie in this choice.

The process works as follows:

  1. During the day, identify all separate infected regions
  2. Determine which region would infect the most uninfected cells if not contained
  3. Build walls completely around that most dangerous region to quarantine it
  4. At night, all non-quarantined infected regions spread to their adjacent uninfected cells
  5. Repeat this process until either all infected regions are quarantined or the entire world becomes infected

Your task is to return the total number of walls used throughout this entire process. If the world becomes fully infected before you can contain all regions, return the number of walls used up to that point.

For example, if you have multiple infected regions and one threatens 3 uninfected cells while another threatens 2, you would quarantine the first region by building walls around its entire perimeter, then let the second region spread overnight before reassessing the situation the next day.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem involves a 2D grid where cells are connected to their 4-directional neighbors. Each infected region forms a connected component, and we need to explore these connections to identify separate regions and their boundaries. This is fundamentally a graph problem where cells are nodes and adjacency represents edges.

Is it a tree?

  • No: The grid structure is not a tree. There can be multiple infected regions (multiple connected components), and within each region, there could be cycles (e.g., a 2x2 block of infected cells forms a cycle).

Is the problem related to directed acyclic graphs?

  • No: The connections between cells are undirected (if cell A is adjacent to cell B, then B is also adjacent to A), and the graph can contain cycles.

Is the problem related to shortest paths?

  • No: We're not finding shortest paths between cells. Instead, we need to identify connected components (infected regions), count their boundaries, and determine which region threatens the most uninfected cells.

Does the problem involve connectivity?

  • Yes: The core of the problem is identifying connected components of infected cells. We need to:
    1. Find all separate infected regions (connected components)
    2. For each region, identify its boundary with uninfected cells
    3. Count the walls needed to contain each region

Does the problem have small constraints?

  • Yes: While not explicitly stated in the problem, grid problems typically have manageable constraints that allow for DFS/BFS exploration. We need to repeatedly traverse the grid to identify regions.

DFS/backtracking?

  • Yes: DFS is perfect for exploring connected components in a grid. For each unvisited infected cell, we use DFS to explore all connected infected cells, marking them as part of the same region while counting walls needed and identifying threatened uninfected cells.

Conclusion: The flowchart suggests using DFS to solve this problem. DFS helps us explore each infected region completely, identify all cells in that region, count the walls needed to contain it, and determine which uninfected cells it threatens.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to simulate the virus containment process day by day. Each day, we face a decision: which infected region should we quarantine? The greedy choice is clear - we should always quarantine the region that threatens the most uninfected cells, as this prevents the maximum spread for the next night.

To implement this strategy, we need to solve several subproblems:

  1. Identify all separate infected regions: Since infected cells form connected components in the grid, we can use DFS to explore each region. Starting from any unvisited infected cell, DFS will naturally traverse all connected infected cells, giving us one complete region.

  2. Count walls needed for each region: As we explore a region with DFS, every time we encounter a boundary between an infected cell and an uninfected cell, we need a wall. The trick is that if an infected region touches the same uninfected cell from multiple sides, we need multiple walls (one for each shared boundary).

  3. Identify threatened uninfected cells: While counting walls, we also track which uninfected cells are adjacent to each infected region. These are the cells that would become infected overnight if we don't quarantine this region. We use a set to avoid counting the same threatened cell multiple times.

  4. Make the greedy choice: After analyzing all regions, we quarantine the one threatening the most unique uninfected cells (the one with the largest boundary set). We mark these quarantined cells with -1 to indicate they're contained and won't spread anymore.

  5. Simulate the spread: For all non-quarantined regions, we let the virus spread to their adjacent uninfected cells. This changes the grid state for the next day.

  6. Repeat until done: We continue this process daily until either all infected regions are quarantined (no more regions found) or the world becomes fully infected.

The beauty of this approach is that DFS naturally handles the exploration of irregular-shaped regions, and by tracking three pieces of information simultaneously (region cells, wall count, and threatened cells), we can make optimal decisions at each step. The solution elegantly combines graph traversal with greedy strategy to solve what initially seems like a complex simulation problem.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation uses a simulation approach with DFS to identify and process infected regions iteratively. Let's walk through the key components:

Main Loop Structure: The solution runs an infinite loop that continues until no infected regions remain. Each iteration represents one day in the simulation.

Data Structures Used:

  • vis: A 2D boolean array to track visited cells during DFS traversal
  • areas: List of lists, where each inner list contains coordinates (i, j) of cells belonging to one infected region
  • boundaries: List of sets, where each set contains coordinates of unique uninfected cells threatened by the corresponding region
  • c: List of integers, where each element counts the total walls needed to quarantine the corresponding region

DFS Implementation: The dfs(i, j) function explores an infected region starting from cell (i, j):

  1. Mark the current cell as visited: vis[i][j] = True
  2. Add the cell to the current region: areas[-1].append((i, j))
  3. Explore all 4 directions [[0, -1], [0, 1], [-1, 0], [1, 0]]
  4. For each neighbor (x, y):
    • If it's an unvisited infected cell (isInfected[x][y] == 1), recursively call DFS
    • If it's an uninfected cell (isInfected[x][y] == 0):
      • Increment wall count: c[-1] += 1 (we need one wall for this boundary)
      • Add to threatened cells set: boundaries[-1].add((x, y))

Daily Process:

  1. Initialize tracking structures for the current day
  2. Identify all infected regions by iterating through the grid and calling DFS on unvisited infected cells
  3. Break if no regions found (all infections contained)
  4. Select the most dangerous region: idx = boundaries.index(max(boundaries, key=len))
    • This finds the region threatening the most unique uninfected cells
  5. Add walls to answer: ans += c[idx]
  6. Process each region:
    • For the selected region (k == idx): Mark all cells as quarantined using -1
    • For other regions: Spread the virus to adjacent uninfected cells by setting them to 1

Key Observations:

  • The wall count c[idx] correctly counts all walls needed because DFS increments the counter for every infected-uninfected boundary encountered
  • Using a set for boundaries ensures each threatened cell is counted only once per region, even if touched from multiple sides
  • Marking quarantined cells as -1 prevents them from being processed in future iterations
  • The virus spread is simulated by changing uninfected neighbors of non-quarantined regions from 0 to 1

Time Complexity: O(m*n*days) where days is the number of iterations needed Space Complexity: O(m*n) for the various tracking structures

The algorithm continues until either all infected regions are successfully quarantined or the infection spreads completely, returning the total number of walls used throughout the process.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Initial grid (3x4):
0 1 1 0
1 1 0 0
0 0 1 0

Day 1:

  1. Identify infected regions using DFS:

    • Starting from (0,1), DFS explores: (0,1) → (0,2) → (1,0) → (1,1)
      • Region 1: [(0,1), (0,2), (1,0), (1,1)]
    • Starting from (2,2), DFS explores: (2,2)
      • Region 2: [(2,2)]

  2. Count walls and threatened cells for each region:

    • Region 1 walls and boundaries:
      • From (0,1): wall to (0,0), so c[0] = 1, boundaries[0] = {(0,0)}
      • From (0,2): wall to (0,3), so c[0] = 2, boundaries[0] = {(0,0), (0,3)}
      • From (1,0): wall to (2,0), so c[0] = 3, boundaries[0] = {(0,0), (0,3), (2,0)}
      • From (1,1): wall to (1,2) and (2,1), so c[0] = 5, boundaries[0] = {(0,0), (0,3), (2,0), (1,2), (2,1)}
      • Total: 5 walls needed, threatens 5 unique cells
    • Region 2 walls and boundaries:
      • From (2,2): walls to (1,2), (2,1), (2,3), so c[1] = 3
      • boundaries[1] = {(1,2), (2,1), (2,3)}
      • Total: 3 walls needed, threatens 3 unique cells

  3. Select most dangerous region:

    • Region 1 threatens 5 cells vs Region 2 threatens 3 cells
    • Choose Region 1 to quarantine
    • Add 5 walls to total: ans = 5

  4. Update grid:

    • Quarantine Region 1 (mark with -1): 
      0 -1 -1 0
-1 -1 0 0
0  0  1 0
    • Let Region 2 spread overnight: 
      0 -1 -1 0
-1 -1 1 0
0  1  1 1

Day 2:

  1. Identify remaining infected regions:

    • Starting from (1,2), DFS explores: (1,2) → (2,1) → (2,2) → (2,3)
    • Region: [(1,2), (2,1), (2,2), (2,3)]

  2. Count walls and threatened cells:

    • From (1,2): walls to (0,2)[-1, skip], (1,1)[-1, skip], (1,3), so c[0] = 1
    • From (2,1): walls to (2,0), (1,1)[-1, skip], so c[0] = 2
    • From (2,2): no new uninfected neighbors
    • From (2,3): no uninfected neighbors on grid
    • Total: 2 walls needed, threatens {(1,3), (2,0)}

  3. Quarantine the only region:

    • Add 2 walls to total: ans = 5 + 2 = 7

  4. Final grid (all infected regions contained):

    0 -1 -1 0
-1 -1 -1 0
0 -1 -1 -1

Result: Total walls used = 7

This example demonstrates how the algorithm:

  • Uses DFS to identify connected infected regions
  • Counts walls needed by checking boundaries with uninfected cells
  • Makes greedy choices to quarantine the most threatening region
  • Simulates virus spread for non-quarantined regions
  • Continues until all infections are contained

Solution Implementation

1class Solution:
2    def containVirus(self, isInfected: List[List[int]]) -> int:
3        def dfs(row: int, col: int) -> None:
4            """
5            Depth-first search to explore a virus region.
6            Collects infected cells, counts walls needed, and identifies threatened cells.
7            """
8            visited[row][col] = True
9            current_region.append((row, col))
10          
11            # Check all 4 adjacent cells
12            for delta_row, delta_col in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
13                new_row, new_col = row + delta_row, col + delta_col
14              
15                if 0 <= new_row < rows and 0 <= new_col < cols:
16                    if isInfected[new_row][new_col] == 1 and not visited[new_row][new_col]:
17                        # Continue exploring infected cells
18                        dfs(new_row, new_col)
19                    elif isInfected[new_row][new_col] == 0:
20                        # Count walls needed and track threatened cells
21                        walls_needed[-1] += 1
22                        threatened_cells[-1].add((new_row, new_col))
23      
24        rows, cols = len(isInfected), len(isInfected[0])
25        total_walls = 0
26      
27        while True:
28            # Initialize tracking structures for this iteration
29            visited = [[False] * cols for _ in range(rows)]
30            infected_regions = []  # List of infected cell coordinates for each region
31            walls_needed = []      # Number of walls needed for each region
32            threatened_cells = []  # Set of uninfected cells threatened by each region
33          
34            # Find all distinct infected regions
35            for i in range(rows):
36                for j in range(cols):
37                    if isInfected[i][j] == 1 and not visited[i][j]:
38                        # Start new region exploration
39                        current_region = []
40                        infected_regions.append(current_region)
41                        threatened_cells.append(set())
42                        walls_needed.append(0)
43                        dfs(i, j)
44          
45            # If no infected regions remain, we're done
46            if not infected_regions:
47                break
48          
49            # Find the region that threatens the most cells
50            most_dangerous_idx = threatened_cells.index(max(threatened_cells, key=len))
51          
52            # Add walls needed for the most dangerous region
53            total_walls += walls_needed[most_dangerous_idx]
54          
55            # Process each region
56            for region_idx, region in enumerate(infected_regions):
57                if region_idx == most_dangerous_idx:
58                    # Quarantine the most dangerous region (mark as contained with -1)
59                    for i, j in region:
60                        isInfected[i][j] = -1
61                else:
62                    # Spread virus from other regions to adjacent uninfected cells
63                    for i, j in region:
64                        for delta_row, delta_col in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
65                            new_row, new_col = i + delta_row, j + delta_col
66                            if (0 <= new_row < rows and 0 <= new_col < cols 
67                                and isInfected[new_row][new_col] == 0):
68                                isInfected[new_row][new_col] = 1
69      
70        return total_walls
71
1class Solution {
2    // Direction vectors for moving up, right, down, left
3    private static final int[] DIRECTIONS = {-1, 0, 1, 0, -1};
4  
5    // List to store the number of walls needed for each infected region
6    private List<Integer> wallCounts = new ArrayList<>();
7  
8    // List to store the infected cells for each region
9    private List<List<Integer>> infectedRegions = new ArrayList<>();
10  
11    // List to store the unique threatened cells for each region
12    private List<Set<Integer>> threatenedCells = new ArrayList<>();
13  
14    // Grid representing the infection status
15    private int[][] grid;
16  
17    // Visited array for DFS traversal
18    private boolean[][] visited;
19  
20    // Grid dimensions
21    private int rows;
22    private int cols;
23
24    public int containVirus(int[][] isInfected) {
25        grid = isInfected;
26        rows = grid.length;
27        cols = grid[0].length;
28        visited = new boolean[rows][cols];
29        int totalWalls = 0;
30      
31        while (true) {
32            // Reset visited array for each iteration
33            for (boolean[] row : visited) {
34                Arrays.fill(row, false);
35            }
36          
37            // Clear all tracking lists for new iteration
38            wallCounts.clear();
39            infectedRegions.clear();
40            threatenedCells.clear();
41          
42            // Find all connected infected regions
43            for (int i = 0; i < rows; i++) {
44                for (int j = 0; j < cols; j++) {
45                    if (grid[i][j] == 1 && !visited[i][j]) {
46                        // Initialize new region tracking
47                        wallCounts.add(0);
48                        infectedRegions.add(new ArrayList<>());
49                        threatenedCells.add(new HashSet<>());
50                      
51                        // Explore the infected region using DFS
52                        exploreRegion(i, j);
53                    }
54                }
55            }
56          
57            // If no infected regions found, we're done
58            if (infectedRegions.isEmpty()) {
59                break;
60            }
61          
62            // Find the region that threatens the most cells
63            int mostDangerousRegionIndex = findMostDangerousRegion(threatenedCells);
64          
65            // Add walls needed for the most dangerous region
66            totalWalls += wallCounts.get(mostDangerousRegionIndex);
67          
68            // Process each region
69            for (int regionIndex = 0; regionIndex < infectedRegions.size(); regionIndex++) {
70                if (regionIndex == mostDangerousRegionIndex) {
71                    // Quarantine the most dangerous region (mark as contained with -1)
72                    for (int cellEncoding : infectedRegions.get(regionIndex)) {
73                        int row = cellEncoding / cols;
74                        int col = cellEncoding % cols;
75                        grid[row][col] = -1;
76                    }
77                } else {
78                    // Spread infection from other regions by one cell
79                    for (int cellEncoding : infectedRegions.get(regionIndex)) {
80                        int row = cellEncoding / cols;
81                        int col = cellEncoding % cols;
82                      
83                        // Check all four directions for spread
84                        for (int dir = 0; dir < 4; dir++) {
85                            int newRow = row + DIRECTIONS[dir];
86                            int newCol = col + DIRECTIONS[dir + 1];
87                          
88                            // Infect healthy adjacent cells
89                            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols 
90                                && grid[newRow][newCol] == 0) {
91                                grid[newRow][newCol] = 1;
92                            }
93                        }
94                    }
95                }
96            }
97        }
98      
99        return totalWalls;
100    }
101
102    /**
103     * Find the region index that threatens the most unique cells
104     */
105    private int findMostDangerousRegion(List<Set<Integer>> threatenedCells) {
106        int mostDangerousIndex = 0;
107        int maxThreatened = threatenedCells.get(0).size();
108      
109        for (int i = 1; i < threatenedCells.size(); i++) {
110            int currentThreatened = threatenedCells.get(i).size();
111            if (maxThreatened < currentThreatened) {
112                maxThreatened = currentThreatened;
113                mostDangerousIndex = i;
114            }
115        }
116      
117        return mostDangerousIndex;
118    }
119
120    /**
121     * DFS to explore an infected region and count walls needed
122     */
123    private void exploreRegion(int row, int col) {
124        visited[row][col] = true;
125        int currentRegionIndex = infectedRegions.size() - 1;
126      
127        // Encode cell position as single integer for storage
128        infectedRegions.get(currentRegionIndex).add(row * cols + col);
129      
130        // Check all four adjacent cells
131        for (int dir = 0; dir < 4; dir++) {
132            int newRow = row + DIRECTIONS[dir];
133            int newCol = col + DIRECTIONS[dir + 1];
134          
135            // Check if new position is within bounds
136            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
137                if (grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
138                    // Continue exploring infected cells
139                    exploreRegion(newRow, newCol);
140                } else if (grid[newRow][newCol] == 0) {
141                    // Count walls needed and track threatened cells
142                    wallCounts.set(currentRegionIndex, wallCounts.get(currentRegionIndex) + 1);
143                    threatenedCells.get(currentRegionIndex).add(newRow * cols + newCol);
144                }
145            }
146        }
147    }
148}
149
1class Solution {
2public:
3    // Direction vectors for 4-directional movement (up, right, down, left)
4    const vector<int> directions = {-1, 0, 1, 0, -1};
5  
6    // Storage for walls needed for each infected region
7    vector<int> wallsNeeded;
8  
9    // Storage for infected cells in each region (encoded as row * n + col)
10    vector<vector<int>> infectedRegions;
11  
12    // Storage for threatened cells for each region (cells that will be infected next day)
13    vector<unordered_set<int>> threatenedCells;
14  
15    // Grid to track infection status
16    vector<vector<int>> grid;
17  
18    // Visited array for DFS traversal
19    vector<vector<bool>> visited;
20  
21    int rows;
22    int cols;
23
24    int containVirus(vector<vector<int>>& isInfected) {
25        grid = isInfected;
26        rows = grid.size();
27        cols = grid[0].size();
28        visited.assign(rows, vector<bool>(cols));
29      
30        int totalWalls = 0;
31      
32        // Continue until no more infected regions can spread
33        while (true) {
34            // Reset visited array for new iteration
35            for (int i = 0; i < rows; ++i) {
36                for (int j = 0; j < cols; ++j) {
37                    visited[i][j] = false;
38                }
39            }
40          
41            // Clear previous iteration's data
42            wallsNeeded.clear();
43            infectedRegions.clear();
44            threatenedCells.clear();
45          
46            // Find all infected regions and their boundaries
47            for (int i = 0; i < rows; ++i) {
48                for (int j = 0; j < cols; ++j) {
49                    if (grid[i][j] == 1 && !visited[i][j]) {
50                        // Initialize new region
51                        wallsNeeded.push_back(0);
52                        infectedRegions.push_back({});
53                        threatenedCells.push_back({});
54                      
55                        // Explore the infected region using DFS
56                        exploreRegion(i, j);
57                    }
58                }
59            }
60          
61            // If no infected regions found, we're done
62            if (infectedRegions.empty()) {
63                break;
64            }
65          
66            // Find the most dangerous region (threatens most cells)
67            int mostDangerousIdx = findMostDangerousRegion();
68          
69            // Add walls needed to contain the most dangerous region
70            totalWalls += wallsNeeded[mostDangerousIdx];
71          
72            // Process all regions
73            for (int regionIdx = 0; regionIdx < infectedRegions.size(); ++regionIdx) {
74                if (regionIdx == mostDangerousIdx) {
75                    // Quarantine the most dangerous region (mark as -1)
76                    for (int encodedPos : infectedRegions[regionIdx]) {
77                        int row = encodedPos / cols;
78                        int col = encodedPos % cols;
79                        grid[row][col] = -1;  // Mark as quarantined
80                    }
81                } else {
82                    // Other regions spread to their threatened cells
83                    for (int encodedPos : infectedRegions[regionIdx]) {
84                        int row = encodedPos / cols;
85                        int col = encodedPos % cols;
86                      
87                        // Check all 4 adjacent cells
88                        for (int dir = 0; dir < 4; ++dir) {
89                            int newRow = row + directions[dir];
90                            int newCol = col + directions[dir + 1];
91                          
92                            // Infect healthy adjacent cells
93                            if (newRow >= 0 && newRow < rows && 
94                                newCol >= 0 && newCol < cols && 
95                                grid[newRow][newCol] == 0) {
96                                grid[newRow][newCol] = 1;
97                            }
98                        }
99                    }
100                }
101            }
102        }
103      
104        return totalWalls;
105    }
106
107private:
108    // Find the region that threatens the most cells
109    int findMostDangerousRegion() {
110        int mostDangerousIdx = 0;
111        int maxThreatened = threatenedCells[0].size();
112      
113        for (int i = 1; i < threatenedCells.size(); ++i) {
114            int currentThreatened = threatenedCells[i].size();
115            if (currentThreatened > maxThreatened) {
116                maxThreatened = currentThreatened;
117                mostDangerousIdx = i;
118            }
119        }
120      
121        return mostDangerousIdx;
122    }
123
124    // DFS to explore an infected region and count walls needed
125    void exploreRegion(int row, int col) {
126        visited[row][col] = true;
127      
128        // Add current cell to the region (encode position as row * cols + col)
129        infectedRegions.back().push_back(row * cols + col);
130      
131        // Check all 4 adjacent cells
132        for (int dir = 0; dir < 4; ++dir) {
133            int newRow = row + directions[dir];
134            int newCol = col + directions[dir + 1];
135          
136            // Check if new position is within bounds
137            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
138                if (grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
139                    // Continue exploring infected cells
140                    exploreRegion(newRow, newCol);
141                } else if (grid[newRow][newCol] == 0) {
142                    // Found a healthy cell that needs a wall
143                    wallsNeeded.back() += 1;
144                  
145                    // Track this threatened cell (use set to avoid duplicates)
146                    threatenedCells.back().insert(newRow * cols + newCol);
147                }
148            }
149        }
150    }
151};
152
1// Direction vectors for 4-directional movement (up, right, down, left)
2const directions: number[] = [-1, 0, 1, 0, -1];
3
4// Storage for walls needed for each infected region
5let wallsNeeded: number[];
6
7// Storage for infected cells in each region (encoded as row * cols + col)
8let infectedRegions: number[][];
9
10// Storage for threatened cells for each region (cells that will be infected next day)
11let threatenedCells: Set<number>[];
12
13// Grid to track infection status
14let grid: number[][];
15
16// Visited array for DFS traversal
17let visited: boolean[][];
18
19// Grid dimensions
20let rows: number;
21let cols: number;
22
23function containVirus(isInfected: number[][]): number {
24    // Initialize grid with the infected status
25    grid = isInfected;
26    rows = grid.length;
27    cols = grid[0].length;
28  
29    // Initialize visited array with false values
30    visited = Array(rows).fill(null).map(() => Array(cols).fill(false));
31  
32    let totalWalls = 0;
33  
34    // Continue until no more infected regions can spread
35    while (true) {
36        // Reset visited array for new iteration
37        for (let i = 0; i < rows; i++) {
38            for (let j = 0; j < cols; j++) {
39                visited[i][j] = false;
40            }
41        }
42      
43        // Clear previous iteration's data
44        wallsNeeded = [];
45        infectedRegions = [];
46        threatenedCells = [];
47      
48        // Find all infected regions and their boundaries
49        for (let i = 0; i < rows; i++) {
50            for (let j = 0; j < cols; j++) {
51                if (grid[i][j] === 1 && !visited[i][j]) {
52                    // Initialize new region with empty arrays and set
53                    wallsNeeded.push(0);
54                    infectedRegions.push([]);
55                    threatenedCells.push(new Set<number>());
56                  
57                    // Explore the infected region using DFS
58                    exploreRegion(i, j);
59                }
60            }
61        }
62      
63        // If no infected regions found, we're done
64        if (infectedRegions.length === 0) {
65            break;
66        }
67      
68        // Find the most dangerous region (threatens most cells)
69        const mostDangerousIdx = findMostDangerousRegion();
70      
71        // Add walls needed to contain the most dangerous region
72        totalWalls += wallsNeeded[mostDangerousIdx];
73      
74        // Process all regions
75        for (let regionIdx = 0; regionIdx < infectedRegions.length; regionIdx++) {
76            if (regionIdx === mostDangerousIdx) {
77                // Quarantine the most dangerous region (mark as -1)
78                for (const encodedPos of infectedRegions[regionIdx]) {
79                    const row = Math.floor(encodedPos / cols);
80                    const col = encodedPos % cols;
81                    grid[row][col] = -1;  // Mark as quarantined
82                }
83            } else {
84                // Other regions spread to their threatened cells
85                for (const encodedPos of infectedRegions[regionIdx]) {
86                    const row = Math.floor(encodedPos / cols);
87                    const col = encodedPos % cols;
88                  
89                    // Check all 4 adjacent cells
90                    for (let dir = 0; dir < 4; dir++) {
91                        const newRow = row + directions[dir];
92                        const newCol = col + directions[dir + 1];
93                      
94                        // Infect healthy adjacent cells
95                        if (newRow >= 0 && newRow < rows && 
96                            newCol >= 0 && newCol < cols && 
97                            grid[newRow][newCol] === 0) {
98                            grid[newRow][newCol] = 1;
99                        }
100                    }
101                }
102            }
103        }
104    }
105  
106    return totalWalls;
107}
108
109// Find the region that threatens the most cells
110function findMostDangerousRegion(): number {
111    let mostDangerousIdx = 0;
112    let maxThreatened = threatenedCells[0].size;
113  
114    for (let i = 1; i < threatenedCells.length; i++) {
115        const currentThreatened = threatenedCells[i].size;
116        if (currentThreatened > maxThreatened) {
117            maxThreatened = currentThreatened;
118            mostDangerousIdx = i;
119        }
120    }
121  
122    return mostDangerousIdx;
123}
124
125// DFS to explore an infected region and count walls needed
126function exploreRegion(row: number, col: number): void {
127    // Mark current cell as visited
128    visited[row][col] = true;
129  
130    // Add current cell to the region (encode position as row * cols + col)
131    infectedRegions[infectedRegions.length - 1].push(row * cols + col);
132  
133    // Check all 4 adjacent cells
134    for (let dir = 0; dir < 4; dir++) {
135        const newRow = row + directions[dir];
136        const newCol = col + directions[dir + 1];
137      
138        // Check if new position is within bounds
139        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
140            if (grid[newRow][newCol] === 1 && !visited[newRow][newCol]) {
141                // Continue exploring infected cells
142                exploreRegion(newRow, newCol);
143            } else if (grid[newRow][newCol] === 0) {
144                // Found a healthy cell that needs a wall
145                wallsNeeded[wallsNeeded.length - 1] += 1;
146              
147                // Track this threatened cell (use set to avoid duplicates)
148                threatenedCells[threatenedCells.length - 1].add(newRow * cols + newCol);
149            }
150        }
151    }
152}
153

Time and Space Complexity

Time Complexity: O(m * n * (m + n))

The algorithm runs in a loop that continues until no more infected regions exist. In the worst case, we might need to quarantine regions O(m * n) times (when each cell becomes infected one at a time).

For each iteration:

  • We traverse the entire grid to find infected regions: O(m * n)
  • The DFS traversal visits each cell at most once: O(m * n)
  • For each infected cell during DFS, we check 4 neighbors: O(1)
  • Finding the maximum boundary set: O(number of regions) which is at most O(m * n)
  • Marking quarantined areas and spreading infection: O(m * n)

Since we might have up to O(min(m * n, m + n)) iterations (practically bounded by the grid's dimensions for spreading), the overall time complexity is O(m * n * (m + n)).

Space Complexity: O(m * n)

The space usage includes:

  • vis array: O(m * n) for each iteration
  • areas list: stores all infected cells, at most O(m * n)
  • boundaries list of sets: stores unique boundary cells, at most O(m * n)
  • c list: stores wall counts for each region, at most O(m * n) regions
  • DFS recursion stack: at most O(m * n) in the worst case when all cells form a single connected component

The dominant space usage is O(m * n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Counting Walls for Shared Boundaries

The Issue: A critical mistake is misunderstanding how walls should be counted when an infected region borders the same uninfected cell from multiple sides. Consider this scenario:

0 1 0
1 1 1
0 1 0

The center infected region touches the top uninfected cell from one side, but if we only count unique threatened cells, we might incorrectly calculate just 4 walls total (one per unique uninfected neighbor) instead of the correct 8 walls (counting each boundary separately).

Why This Happens: Developers often confuse two different metrics:

  • The number of unique uninfected cells threatened (used to determine which region to quarantine)
  • The total number of walls needed (every infected-uninfected boundary needs a wall)

The Solution: The code correctly handles this by:

  1. Using a set for threatened_cells to count unique uninfected cells (for region selection)
  2. Using a counter walls_needed that increments for every boundary encountered (for wall counting)
elif isInfected[new_row][new_col] == 0:
    walls_needed[-1] += 1  # Count EVERY boundary
    threatened_cells[-1].add((new_row, new_col))  # Count UNIQUE cells

Pitfall 2: Virus Spreading During the Wrong Phase

The Issue: Another common mistake is spreading the virus immediately when exploring regions with DFS, rather than waiting until after quarantine decisions are made. This would cause the simulation to behave incorrectly, as the virus should only spread at night after walls are built during the day.

Why This Happens: It's tempting to modify the grid during DFS exploration for efficiency, but this violates the problem's day/night cycle where:

  1. Day: Analyze regions and build walls
  2. Night: Non-quarantined regions spread

The Solution: The code maintains proper timing by:

  1. Using DFS only for analysis (collecting region data without modifying the grid)
  2. Modifying the grid only after selecting the quarantine target:
    • Mark quarantined cells as -1
    • Spread virus from non-quarantined regions to adjacent cells
# First analyze all regions without modification
for i in range(rows):
    for j in range(cols):
        if isInfected[i][j] == 1 and not visited[i][j]:
            # Only collect data, don't modify
            dfs(i, j)

# Then modify the grid based on decisions
for region_idx, region in enumerate(infected_regions):
    if region_idx == most_dangerous_idx:
        # Quarantine
        for i, j in region:
            isInfected[i][j] = -1
    else:
        # Spread virus
        for i, j in region:
            # Spread to adjacent uninfected cells

Pitfall 3: Not Handling Already Quarantined Regions

The Issue: Failing to properly mark quarantined regions can cause them to be processed again in subsequent iterations, leading to incorrect wall counts or infinite loops.

Why This Happens: Simply changing quarantined cells to 0 (uninfected) would make them vulnerable to reinfection from neighboring regions. Leaving them as 1 would cause them to be processed again.

The Solution: The code uses -1 as a special marker for quarantined cells:

  • They won't be considered as infected (== 1) in future DFS explorations
  • They won't be treated as uninfected (== 0) targets for virus spread
  • This effectively removes them from all future processing
if isInfected[i][j] == 1 and not visited[i][j]:  # Skips -1 values
    # Process only active infected regions
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

DFS Fundamentals

https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More