Contain Virus : Deep, Intuitive & Fully Explained Guide

HackFury

Last Updated : 30 April 2026

82 Views

#greedy

#data-structures

#coding-problems

#dsa

#depth-first-search

Adℹ

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

Examples

Example 1

Input\nisInfected = \n[[0,1,0,0,0,0,0,1],\n [0,1,0,0,0,0,0,1],\n [0,0,0,0,0,0,0,1],\n [0,0,0,0,0,0,0,0]]\n\nOutput : 10\n

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.\nGrid after spread becomes:

\n[[0,1,0,0,0,0,1,1],\n [0,1,0,0,0,0,1,1],\n [0,0,0,0,0,0,1,1],\n [0,0,0,0,0,0,0,1]]\n\n

(Left region remains unchanged because it is quarantined)

Day 2 : Quarantine Remaining Region

Now only one active region (right side) exists.\nWalls required to isolate it = 5

Final Result

Day 1 walls = 5
Day 2 walls = 5
Total walls = 10

Example 2

Input\nisInfected = \n[ [1,1,1],\n  [1,0,1],\n  [1,1,1]]\n\nOutput : 4\n

Explanation

Initial Observation\nHere, 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.\nNow, observe carefully:

The infected region surrounds the center cell from all four directions.\nSo, the virus can spread into the center cell from:\nTop, Bottom, Left, Right

To completely block this, we need to place walls on all 4 sides of the center cell.\nWalls required = 4

Night 1 : Virus Spread

Since the infected region is now fully quarantined, the virus cannot spread.\nThe 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.\nLet’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).\nFor each such starting point, we discover a region (a connected component of 1s).\nWhile 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:

\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n

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.\nWhy 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\nMark 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.\nFor each region, convert all its frontier cells (0) → infected (1)\nWhy 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\nEntire grid becomes infected.

\n#include <bits/stdc++.h>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<vector<int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};\n    \n    int containVirus(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size();\n        int totalWalls = 0;\n        while (true) {\n            vector<vector<pair<int,int>>> regions;\n            vector<unordered_set<int>> frontiers;\n            vector<int> walls;\n            vector<vector<bool>> visited(m, vector<bool>(n, false));\n            // Step 1: Find regions\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    if (grid[i][j] == 1 && !visited[i][j]) {\n                        vector<pair<int,int>> region;\n                        unordered_set<int> frontier;\n                        int wallCount = 0;\n                        dfs(grid, i, j, visited, region, frontier, wallCount);\n                        regions.push_back(region);\n                        frontiers.push_back(frontier);\n                        walls.push_back(wallCount);\n                    }\n                }\n            }\n\n            if (regions.empty()) break;\n            // Step 2: Find most dangerous region\n            int maxIdx = 0;\n            for (int i = 1; i < frontiers.size(); i++) {\n                if (frontiers[i].size() > frontiers[maxIdx].size()) {\n                    maxIdx = i;\n                }\n            }\n            if (frontiers[maxIdx].empty()) break;\n            // Step 3: Build walls\n            totalWalls += walls[maxIdx];\n            // Step 4: Quarantine\n            for (auto& cell : regions[maxIdx]) {\n                grid[cell.first][cell.second] = -1;\n            }\n            // Step 5: Spread\n            for (int i = 0; i < regions.size(); i++) {\n                if (i == maxIdx) continue;\n                for (int code : frontiers[i]) {\n                    int x = code / n;\n                    int y = code % n;\n                    grid[x][y] = 1;\n                }\n            }\n        }\n        return totalWalls;\n    }\n\nprivate:\n    void dfs(vector<vector<int>>& grid, int i, int j,\n             vector<vector<bool>>& visited,\n             vector<pair<int,int>>& region,\n             unordered_set<int>& frontier,\n             int& wallCount) {\n\n        int m = grid.size(), n = grid[0].size();\n        visited[i][j] = true;\n        region.push_back({i,j});\n        for (auto& d : dirs) {\n            int x = i + d[0], y = j + d[1];\n            if (x < 0 || y < 0 || x >= m || y >= n) continue;\n            if (grid[x][y] == 0) {\n                wallCount++;\n                frontier.insert(x * n + y);\n            } else if (grid[x][y] == 1 && !visited[x][y]) {\n                dfs(grid, x, y, visited, region, frontier, wallCount);\n            }\n        }\n    }\n};\n

\nimport java.util.*;\n\nclass Solution {\n    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};\n    \n    public int containVirus(int[][] grid) {\n        int m = grid.length, n = grid[0].length;\n        int totalWalls = 0;\n        while (true) {\n            List<List<int[]>> regions = new ArrayList<>();\n            List<Set<Integer>> frontiers = new ArrayList<>();\n            List<Integer> walls = new ArrayList<>();\n            boolean[][] visited = new boolean[m][n];\n            // Step 1: Identify all regions\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    if (grid[i][j] == 1 && !visited[i][j]) {\n                        List<int[]> region = new ArrayList<>();\n                        Set<Integer> frontier = new HashSet<>();\n                        int[] wallCount = new int[1];\n                        dfs(grid, i, j, visited, region, frontier, wallCount);\n                        regions.add(region);\n                        frontiers.add(frontier);\n                        walls.add(wallCount[0]);\n                    }\n                }\n            }\n            if (regions.isEmpty()) break;\n            // Step 2: Find most dangerous region\n            int maxIdx = 0;\n            for (int i = 1; i < frontiers.size(); i++) {\n                if (frontiers.get(i).size() > frontiers.get(maxIdx).size()) {\n                    maxIdx = i;\n                }\n            }\n            // If no spread possible\n            if (frontiers.get(maxIdx).isEmpty()) break;\n            // Step 3: Build walls\n            totalWalls += walls.get(maxIdx);\n            // Step 4: Quarantine region\n            for (int[] cell : regions.get(maxIdx)) {\n                grid[cell[0]][cell[1]] = -1;\n            }\n            // Step 5: Spread virus\n            for (int i = 0; i < regions.size(); i++) {\n                if (i == maxIdx) continue;\n                for (int code : frontiers.get(i)) {\n                    int x = code / n;\n                    int y = code % n;\n                    grid[x][y] = 1;\n                }\n            }\n        }\n\n        return totalWalls;\n    }\n\n    private void dfs(int[][] grid, int i, int j, boolean[][] visited,\n                     List<int[]> region, Set<Integer> frontier, int[] wallCount) {\n\n        int m = grid.length, n = grid[0].length;\n        visited[i][j] = true;\n        region.add(new int[]{i, j});\n        for (int[] d : dirs) {\n            int x = i + d[0], y = j + d[1];\n            if (x < 0 || y < 0 || x >= m || y >= n) continue;\n            if (grid[x][y] == 0) {\n                wallCount[0]++;\n                frontier.add(x * n + y);\n            } else if (grid[x][y] == 1 && !visited[x][y]) {\n                dfs(grid, x, y, visited, region, frontier, wallCount);\n            }\n        }\n    }\n}\n

\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    int[][] dirs = new int[][] {\n        new int[]{1,0}, new int[]{-1,0},\n        new int[]{0,1}, new int[]{0,-1}\n    };\n\n    public int ContainVirus(int[][] grid) {\n        int m = grid.Length, n = grid[0].Length;\n        int totalWalls = 0;\n        while (true) {\n            var regions = new List<List<(int,int)>>();\n            var frontiers = new List<HashSet<int>>();\n            var walls = new List<int>();\n            bool[,] visited = new bool[m, n];\n            // Step 1: Find regions\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    if (grid[i][j] == 1 && !visited[i,j]) {\n                        var region = new List<(int,int)>();\n                        var frontier = new HashSet<int>();\n                        int wallCount = 0;\n                        DFS(grid, i, j, visited, region, frontier, ref wallCount);\n                        regions.Add(region);\n                        frontiers.Add(frontier);\n                        walls.Add(wallCount);\n                    }\n                }\n            }\n            if (regions.Count == 0) break;\n            // Step 2: Find most dangerous region\n            int maxIdx = 0;\n            for (int i = 1; i < frontiers.Count; i++) {\n                if (frontiers[i].Count > frontiers[maxIdx].Count) {\n                    maxIdx = i;\n                }\n            }\n            if (frontiers[maxIdx].Count == 0) break;\n            // Step 3: Build walls\n            totalWalls += walls[maxIdx];\n            // Step 4: Quarantine\n            foreach (var cell in regions[maxIdx]) {\n                grid[cell.Item1][cell.Item2] = -1;\n            }\n            // Step 5: Spread\n            for (int i = 0; i < regions.Count; i++) {\n                if (i == maxIdx) continue;\n                foreach (int code in frontiers[i]) {\n                    int x = code / n;\n                    int y = code % n;\n                    grid[x][y] = 1;\n                }\n            }\n        }\n        return totalWalls;\n    }\n\n    private void DFS(int[][] grid, int i, int j, bool[,] visited,\n                     List<(int,int)> region, HashSet<int> frontier, ref int wallCount) {\n\n        int m = grid.Length, n = grid[0].Length;\n        visited[i,j] = true;\n        region.Add((i,j));\n\n        foreach (var d in dirs) {\n            int x = i + d[0], y = j + d[1];\n            if (x < 0 || y < 0 || x >= m || y >= n) continue;\n            if (grid[x][y] == 0) {\n                wallCount++;\n                frontier.Add(x * n + y);\n            } else if (grid[x][y] == 1 && !visited[x,y]) {\n                DFS(grid, x, y, visited, region, frontier, ref wallCount);\n            }\n        }\n    }\n}\n

\nclass Solution:\n    def containVirus(self, grid):\n        m, n = len(grid), len(grid[0])\n        dirs = [(1,0), (-1,0), (0,1), (0,-1)]\n        total_walls = 0\n\n        def dfs(i, j, visited, region, frontier):\n            stack = [(i, j)]\n            visited[i][j] = True\n            walls = 0\n            while stack:\n                x, y = stack.pop()\n                region.append((x, y))\n                for dx, dy in dirs:\n                    nx, ny = x + dx, y + dy\n                    if nx < 0 or ny < 0 or nx >= m or ny >= n:\n                        continue\n                    if grid[nx][ny] == 0:\n                        walls += 1\n                        frontier.add(nx * n + ny)\n                    elif grid[nx][ny] == 1 and not visited[nx][ny]:\n                        visited[nx][ny] = True\n                        stack.append((nx, ny))\n            return walls\n\n        while True:\n            visited = [[False]*n for _ in range(m)]\n            regions, frontiers, walls = [], [], []\n            # Step 1: Find regions\n            for i in range(m):\n                for j in range(n):\n                    if grid[i][j] == 1 and not visited[i][j]:\n                        region = []\n                        frontier = set()\n                        wall_count = dfs(i, j, visited, region, frontier)\n                        regions.append(region)\n                        frontiers.append(frontier)\n                        walls.append(wall_count)\n            if not regions:\n                break\n            # Step 2: Find most dangerous region\n            max_idx = max(range(len(frontiers)), key=lambda i: len(frontiers[i]))\n            if len(frontiers[max_idx]) == 0:\n                break\n            # Step 3: Build walls\n            total_walls += walls[max_idx]\n            # Step 4: Quarantine\n            for x, y in regions[max_idx]:\n                grid[x][y] = -1\n            # Step 5: Spread\n            for i in range(len(regions)):\n                if i == max_idx:\n                    continue\n                for code in frontiers[i]:\n                    x, y = code // n, code % n\n                    grid[x][y] = 1\n\n        return total_walls\n

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

","categoryId":177,"subCategoryId":177,"contentFormat":5,"blogId":90,"userId":"MjlfNF84LVs0XTJuLXRDX0FOZ2VfX0l0","title":"Contain Virus : Deep, Intuitive & Fully Explained Guide","url":"contain-virus-deep-intuitive-fully-explained-guide","bannerImage":"","seoDescription":"Contain Virus problem explained with DFS + greedy approach, step-by-step simulation, examples and optimized solutions for coding interviews.","generatedOn":"2026-04-30T19:43:26","updatedOn":"2026-04-30T19:43:26"},"popularContents":[{"id":213,"title":"Amazon SDE II Interview Experience (Bangalore, Selected) ~ Aug 2026","url":"amazon-sde-ii-interview-experience-bangalore-selected-aug-2026","description":null,"seoDescription":"Amazon SDE II interview experience from Bangalore covering 4 rounds, DSA, LLD, system design, Leadership Principles, coding questions and selection.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184492Z","viewCount":0},{"id":153,"title":"Visa Software Engineer 1 (SDE-1) Interview Experience | CodeSignal OA + Graph-Based Technical Rounds","url":"visa-software-engineer-1-sde-1-interview-experience-codesignal-oa-graph-based-technical-rounds","description":null,"seoDescription":" Ace your Visa SDE-1 interview with this complete interview experience covering CodeSignal OA, graph coding rounds, hiring manager questions and tips.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184474Z","viewCount":0},{"id":122,"title":"Zepto SDE-1 Interview Experience (Backend Developer) : Real DSA, LLD, Chess Game Design","url":"zepto-sde-1-interview-experience-backend-developer-real-dsa-lld-chess-game-design","description":null,"seoDescription":" Zepto SDE-1 Backend Interview Experience covering DSA, Dynamic Programming, LLD, API Design, DB Schema, OOP & Product Company Rounds.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184422Z","viewCount":0},{"id":163,"title":"Top 50 SQL Interview Questions and Answers (Beginner to Intermediate)","url":"top-sql-interview-questions-and-answers-beginner-to-intermediate","description":null,"seoDescription":"Top 50 SQL Interview Questions and Answers (Beginner to Intermediate). Top SQL Interview Questions for fresher. Frequently asked SQL interview questions with answers","contentType":2,"generatedOn":"2026-10-14T22:53:45.2176462Z","viewCount":0},{"id":197,"title":"My Adobe SDE Interview Experience (Aug 2026) 5 Rounds, Selected","url":"my-adobe-sde-interview-experience-aug-2026-5-rounds-selected","description":null,"seoDescription":"Real Adobe SDE interview: 5 rounds, 4 DSA problems (Rotate Array, BSTs, Kth Smallest Matrix), code review & behavioral round. Full solutions + tips.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184484Z","viewCount":0},{"id":118,"title":"JioHotstar Staff Software Engineer Interview Experience (Bangalore)","url":"jiohotstar-staff-software-engineer-interview-experience-bangalore","description":null,"seoDescription":"JioHotstar Staff Software Engineer interview experience covering Uber system design, API rate limiter LLD, leadership rounds, bar raiser and HR insights.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184412Z","viewCount":0},{"id":35,"title":"Cursor vs Copilot : Which AI Coding Assistant Wins in 2025?","url":"cursor-vs-copilot-which-ai-coding-assistant-truly-wins-in-2025","description":null,"seoDescription":"Compare Cursor vs GitHub Copilot on speed, context awareness, multi-file support, pricing and code quality to choose the best AI coding assistant for developers","contentType":5,"generatedOn":"2026-10-14T22:53:45.21844Z","viewCount":0},{"id":135,"title":"Spinny SDE-1 Interview Experience (Selected)","url":"spinny-sde-1-interview-experience-selected","description":null,"seoDescription":"Spinny SDE-1 Interview Experience (Selected) | 4 Rounds Breakdown: Coding, LLD, Java, SQL + Real Interview Questions","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184433Z","viewCount":0},{"id":34,"title":"System Design Deep Dive: 25 Essential Interview Questions","url":"system-design-deep-dive-25-essential-interview-questions","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:53:45.2184368Z","viewCount":0},{"id":165,"title":"Top 50+ SQL Interview Questions and Answers for Intermediate to Advanced","url":"top-sql-interview-questions-and-answers-for-intermediate-to-advanced","description":null,"seoDescription":"Top SQL Interview Questions and Answers for Intermediate to Advanced. Top SQL Interview Questions for experience. Frequently asked SQL interview questions with answers","contentType":2,"generatedOn":"2026-10-14T22:53:45.2176508Z","viewCount":0}],"latestContents":[{"id":219,"title":"6 Tools That Made My Life Easier as a Software Engineer","url":"6-tools-that-made-my-life-easier-as-a-software-engineer","description":null,"seoDescription":"The 6 developer tools I use daily as a software engineer: Git, VS Code, Docker, Postman, Chrome DevTools, and AI assistants, with real tips, mistakes, and trade","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177827Z","viewCount":0},{"id":218,"title":"When Should a Business Use Multiple AI Agents Instead of One?","url":"when-should-a-business-use-multiple-ai-agents-instead-of-one","description":null,"seoDescription":"Single agent or multi-agent AI? Learn the 4 signals that justify splitting agents by knowledge, permissions, and risk, plus routing and handoff tips.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177866Z","viewCount":0},{"id":216,"title":"AI in Clinical Trials Market Estimated to Experience a Hike in Growth by 2035","url":"ai-in-clinical-trials-market-estimated-to-experience-a-hike-in-growth-by-2035","description":null,"seoDescription":"The exclusive information about market dynamics serves as a valuable guide to predict economic scenarios and initiatives taken to enhance future growth. Our mar","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177876Z","viewCount":0},{"id":217,"title":"AI in Clinical Trials Market Estimated to Experience a Hike in Growth by 2035","url":"ai-in-clinical-trials-market-estimated-to-experience-a-hike-in-growth-by-2035","description":null,"seoDescription":"The exclusive information about market dynamics serves as a valuable guide to predict economic scenarios and initiatives taken to enhance future growth. Our mar","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177905Z","viewCount":0},{"id":215,"title":"What Happens When an AI Agent Doesn't Know the Answer?","url":"what-happens-when-an-ai-agent-doesnt-know-the-answer","description":null,"seoDescription":"Most AI agents fail quietly. They guess instead of saying \"I don't know.\" Here's how to design better fallback and human-handoff behavior.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177913Z","viewCount":0},{"id":214,"title":"Greedy Algorithms Explained: How They Work, When They Fail and How to Use Them","url":"greedy-algorithms-explained-how-they-work-when-they-fail-and-how-to-use-them","description":null,"seoDescription":"Learn greedy algorithms step by step with C# code Dijkstra, Huffman coding, knapsack and MSTs plus when greedy fails and how to prove it's correct","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177924Z","viewCount":0},{"id":213,"title":"Amazon SDE II Interview Experience (Bangalore, Selected) ~ Aug 2026","url":"amazon-sde-ii-interview-experience-bangalore-selected-aug-2026","description":null,"seoDescription":"Amazon SDE II interview experience from Bangalore covering 4 rounds, DSA, LLD, system design, Leadership Principles, coding questions and selection.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177934Z","viewCount":0},{"id":212,"title":"How to Get 10x Better AI Answers Without Writing Better Prompts : 10 Proven Techniques","url":"how-to-get-10x-better-ai-answers-without-writing-better-prompts-10-proven-techniques","description":null,"seoDescription":"Get better AI answers without complex prompts. Learn 10 practical techniques using context, examples, tools, feedback, and verification.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177943Z","viewCount":0},{"id":211,"title":"I Interviewed for a Microsoft SDE I Role. Here's Everything That Happened.","url":"i-interviewed-for-a-microsoft-sde-i-role-heres-everything-that-happened","description":null,"seoDescription":"My real Microsoft SDE I interview experience, all 4 rounds, the exact DSA problems with fully tested solutions, the WhatsApp system design round","contentType":5,"generatedOn":"2026-10-14T22:53:45.2177951Z","viewCount":0},{"id":140,"title":"PolicyBazaar Software Development Engineer (SDE) Interview Experience | DSA, Core CS & System Design","url":"policybazaar-software-development-engineer-sde-interview-experience-dsa-core-cs-system-design","description":null,"seoDescription":"Detailed PolicyBazaar SDE interview experience covering 3 rounds: DSA coding, core CS assessment and system design with key learnings and insights.","contentType":5,"generatedOn":"2026-10-14T22:53:45.217796Z","viewCount":0}],"relatedContents":[{"id":207,"title":"How to Find the Right View of a Binary Tree","url":"right-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the right view of a binary tree using DFS and BFS, with examples, code, complexity analysis and coding interview tips.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234596Z","viewCount":0},{"id":206,"title":"Left View of a Binary Tree: DFS and BFS Approaches Explained","url":"left-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the left view of a binary tree using DFS and BFS, with examples, code, complexity analysis, common mistakes and interview tips.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234638Z","viewCount":0},{"id":205,"title":"Top View of a Binary Tree Using BFS and DFS | Complete Guide","url":"top-view-of-a-binary-tree","description":null,"seoDescription":"Learn how to find the top view of a binary tree using DFS and BFS with step-by-step explanations, examples, code, complexity analysis and interview insights.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234655Z","viewCount":0},{"id":201,"title":"Bottom View of a Binary Tree: DFS vs BFS Approach","url":"bottom-view-of-a-binary-tree-dfs-vs-bfs-approach","description":null,"seoDescription":"Learn to find the bottom view of a binary tree using horizontal distance. Compares a buggy DFS attempt, a fixed DFS and the optimal BFS solution in Java.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234669Z","viewCount":0},{"id":200,"title":" Longest Playlist With No Repeated Songs : Brute Force to Optimal","url":"longest-playlist-with-no-repeated-songs-brute-force-to-optimal","description":null,"seoDescription":"Find the longest playlist with no repeated songs using brute force, HashSet, and HashMap sliding window techniques, with Java code and dry runs.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234708Z","viewCount":0},{"id":37,"title":"Find the repeating and missing numbers","url":"find-the-repeating-and-missing-numbers","description":null,"seoDescription":"Find the repeating and missing numbers in an array from 1..n using brute force, hashmap, math and XOR, step-by-step explained with real-world use cases.","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234738Z","viewCount":0},{"id":27,"title":"4 Sum | Find Quads that add up to a target value","url":"4-sum-find-quads-that-add-up-to-a-target-value","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234753Z","viewCount":0},{"id":26,"title":"Top 50 Most Frequently Asked String Coding Problems (Interview Preparation )","url":"top-50-most-frequently-asked-string-coding-problems-interview-preparation","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234765Z","viewCount":0},{"id":25,"title":"Intersection of Two Sorted Arrays","url":"intersection-of-two-sorted-arrays","description":null,"seoDescription":"","contentType":5,"generatedOn":"2026-10-14T22:53:45.2234778Z","viewCount":0}]}}},"source":{"isMobile":false}}; window.__CLIENT_RENDER__ = false;

Contain Virus : Deep, Intuitive & Fully Explained Guide

Examples

Example 1

Explanation

Example 2

Explanation

Step-by-Step Approach

Step 1: Traverse Grid & Find Regions

Step 2: Evaluate Each Region

Step 3: Pick the Most Dangerous Region

Step 4: Build Walls

Step 5: Spread Virus

Step 6: Repeat Until No Spread Possible

Complexity Analysis

Trending Developer Reads

Examples

Example 1

Explanation

Example 2

Explanation

Step-by-Step Approach

Step 1: Traverse Grid & Find Regions

Step 2: Evaluate Each Region

Step 3: Pick the Most Dangerous Region

Step 4: Build Walls

Step 5: Spread Virus

Step 6: Repeat Until No Spread Possible

Complexity Analysis