Contain Virus - Solution & Explanation

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.