Skip to main content
Talentd

Contain Virus - Solution & Explanation

HardArrayDepth-First SearchBreadth-First SearchMatrix13 min readAsked at: Google, Flipkart, Bloomberg
Practice this problem

Problem Statement

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.length
  • n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] is either 0 or 1.
  • There is always a contiguous viral region throughout the described process that will infect strictly more uncontaminated squares in the next round.

Approach Overview

Problem Overview: You are given a grid where 1 represents infected cells and 0 represents uninfected cells. Each day, the virus spreads to neighboring cells unless you quarantine one infected region by building walls around it. The goal is to repeatedly identify the region that threatens the most new cells, build walls around it, and allow the remaining regions to spread. Return the total number of walls built during the process.

The challenge is identifying infected regions, measuring their potential spread (frontier cells), and simulating the daily containment process. Each iteration requires exploring connected components, tracking boundaries, and updating the grid state. Graph traversal techniques like Breadth-First Search and Depth-First Search work naturally because the grid behaves like a graph where each cell connects to its four neighbors.

Approach 1: Breadth-First Search (BFS) for Contaminated Regions (Time: O((m*n)^2), Space: O(m*n))

Scan the grid each day and start a BFS whenever you encounter an unvisited infected cell. The BFS collects all cells in the same infected region, tracks the neighboring healthy cells that could be infected next (the frontier), and counts the number of walls required to isolate the region. Store this information for every region discovered during the scan. After processing all regions, select the region with the largest frontier and quarantine it by converting its cells to a blocked state.

The remaining regions spread normally. Iterate through their frontier cells and convert those healthy cells to infected ones. Repeat the process until no region can spread further. BFS is intuitive for layer-by-layer exploration and works well when you want to track neighboring cells and boundaries in a matrix grid.

Approach 2: Depth-First Search (DFS) for Contaminated Regions (Time: O((m*n)^2), Space: O(m*n))

The DFS version follows the same containment strategy but explores regions using recursion or an explicit stack. When you encounter an infected cell, run DFS to collect all connected infected cells, record the unique healthy neighbors they threaten, and count the required walls along the boundary. Each DFS call marks visited cells so the same region is not processed twice.

After identifying all regions, select the one threatening the most cells and quarantine it. Mark its cells as contained, while the other regions expand into their frontier cells. Continue repeating the detection and spread cycle until no infected region can grow further. DFS often produces simpler implementations when recursively exploring connected components in grid-based simulation problems.

Recommended for interviews: Both BFS and DFS solutions are acceptable because the core challenge is the simulation logic, not the traversal method. Interviewers typically expect you to model regions, track frontier cells with sets, and repeatedly quarantine the most dangerous region. A correct implementation with O((m*n)^2) time complexity demonstrates strong grid traversal and simulation skills.

Approach 1: Breadth-First Search (BFS) for Contaminated Regions

This approach uses BFS to explore each contaminated region and calculate the number of walls needed to quarantine it. We visit each cell in the grid and use BFS to collect all connected infected cells into a region while counting uninfected neighbors and the walls needed. We then prioritize based on the number of cells threatened.

The BFS approach starts by iterating over each cell in the grid. For each new contaminated cell (not previously visited), it initiates a BFS to explore the entire contiguous region of infected cells. During this BFS, we collect cells that are part of the region, count neighboring uninfected cells, and calculate how many walls are required. The regions are prioritized by the number of uninfected cells they threaten. On each 'day', we choose the most dangerous region to quarantine, mark it, and allow other regions to spread.

Code

PythonJava

Python

Java

Complexity

Time complexity is O(m * n) in worst-case since we potentially visit each cell once. Each BFS operation processes all cells in the connected components and calculates using neighbor checks. Space complexity is also O(m * n) due to additional data structures used for bfs state.

Try this approach in the editor β†’

Approach 2: Depth-First Search (DFS) for Contaminated Regions

This approach leverages DFS to explore and manage the infected regions. Similar to BFS, DFS identifies contiguous regions, evaluates threats to nearby uninfected cells, and calculates the required protective walls. DFS is suitable due to its natural recursion stack management for exploring all paths fully per region.

This C++ implementation uses DFS to explore each region of infected cells. Each call to DFS processes all cells reachable from the starting cell, calculates the surrounding walls required for containment, and collects nearby uninfected neighbors as potential new infection threats. DFS naturally traverses deeper paths first before backing up, making it well-suited for full region exploration here.

Code

C++JavaScript

C++

JavaScript

Complexity

The time complexity of the DFS implementation is O(m * n), due to examining each cell individually and performing DFS requiring additional path exploration. Space complexity is similar, O(m * n), from recursion stack depth and temporary data for regions and threats compound.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) for Contaminated Regions

Time complexity is O(m * n) in worst-case since we potentially visit each cell once. Each BFS operation processes all cells in the connected components and calculates using neighbor checks. Space complexity is also O(m * n) due to additional data structures used for bfs state.

Depth-First Search (DFS) for Contaminated Regions

The time complexity of the DFS implementation is O(m * n), due to examining each cell individually and performing DFS requiring additional path exploration. Space complexity is similar, O(m * n), from recursion stack depth and temporary data for regions and threats compound.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS for Contaminated RegionsO((m*n)^2)O(m*n)When you prefer queue-based level traversal and explicit frontier tracking
DFS for Contaminated RegionsO((m*n)^2)O(m*n)When implementing recursive connected-component exploration in grid problems

Video Solution

θŠ±θŠ±ι…± LeetCode 749. Contain Virus - εˆ·ι’˜ζ‰Ύε·₯作 EP136 β€’ Hua Hua β€’ 3,727 views views

Watch 8 more video solutions β†’

Frequently Asked Questions

Is Contain Virus easy or hard?
Contain Virus is classified as a Hard problem because it combines graph traversal with multi-step simulation. You must correctly track infected regions, count required walls, manage frontier cells, and update the grid across several iterations without double counting.
Contain Virus Python/Java solution
Python and Java implementations usually follow the same structure: scan the grid, run BFS or DFS to detect regions, record frontier cells and required walls, quarantine the largest region, and allow the others to spread. The simulation continues until no infected region can expand.
How to solve Contain Virus in O(n)?
Contain Virus cannot realistically be solved in strict O(n) time because the grid must be re-evaluated across multiple simulation rounds. Each round requires discovering regions and evaluating their boundaries. The accepted approach uses repeated BFS or DFS traversals, resulting in roughly O((m*n)^2) time complexity in the worst case.
What is the best approach for Contain Virus?
The standard solution simulates the spread of infection while repeatedly quarantining the most dangerous region. Each day you detect infected regions using BFS or DFS, count how many healthy cells each region threatens, and build walls around the region with the largest frontier. This simulation runs in O((m*n)^2) time because the grid may be scanned multiple times.
Is Contain Virus asked at Google/Amazon/Meta?
Contain Virus is considered a high-level grid simulation problem and has appeared in advanced interview preparation lists for companies like Google and Meta. It tests graph traversal, connected components, and careful state simulation across multiple iterations.
What data structure is used in Contain Virus?
The solution primarily uses grid traversal structures such as queues for BFS or recursion/stack for DFS. Additional data structures include sets to track frontier cells threatened by each region and arrays or matrices to mark visited cells during traversal.
What is the time complexity of Contain Virus?
The typical BFS or DFS simulation runs in O((m*n)^2) time where m and n are the grid dimensions. Each iteration scans the grid to detect regions and may repeat until no further spread occurs. Space complexity is O(m*n) for visited tracking, region storage, and frontier sets.

Ready to solve this problem?

Practice Contain Virus with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Infection Sequences