Contain Virus
Asked at Flipkart
Problem
Contain Virus simulates an outbreak on a grid: each day you can wall off the single infected region that threatens the most uninfected cells, and then every other region spreads to its neighbors. The task is to return the total number of walls built. It is a long simulation that rewards clean decomposition into "find regions", "pick one", "wall it", and "spread".
Asked At
| Company | Difficulty | |
|---|---|---|
| Flipkart | Hard | View all Flipkart questions → |
How to Think About It
Each day has three phases: identify every connected infected region, quarantine the most threatening one, and let the rest spread by one cell in all four directions.
For each region, collect three things in one DFS/BFS: its cells, the set of distinct uninfected neighbor cells it threatens, and the number of walls it would need (count every infected-to-uninfected edge, not distinct cells).
Pick the region with the largest threatened set (the problem guarantees no ties). Add its wall count to the answer and mark its cells as contained (for example with 2) so they never spread again.
Every other region infects all of its threatened cells. Then start the next day. Stop when no region threatens any cell.
Why walls and threatened cells differ: one uninfected cell can touch the region on several sides, needing several walls but counting as one threatened cell.
Optimal Approach
Loop:
Step 1: Find all regions of 1s with BFS. For each, record cells, threat (set of adjacent 0 cells), and walls (count of adjacent 0 edges).
Step 2: If there are no regions or the largest threat is empty, stop.
Step 3: Pick the region i with the largest threat. total += walls[i]. Mark its cells as 2.
Step 4: For every other region, set each cell in its threat to 1.
Return total.
Time: O((m * n)^(4/3)) in the worst case (each day is O(m * n) and the number of days is bounded). Space: O(m * n).
What Trips People Up in Real Interviews
Counting threatened cells instead of walls for the answer. A cell touching the region on two sides needs two walls.
Choosing the region by wall count. The region to quarantine is the one threatening the most cells.
Letting quarantined cells spread later. Mark them with a distinct value so they are ignored in future days.
Spreading while still scanning for regions. Collect everything for the day first, then apply the spread.
Solution Code
from collections import deque
def containVirus(isInfected):
g = isInfected
m, n = len(g), len(g[0])
total = 0
while True:
seen = [[False] * n for _ in range(m)]
regions, threats, walls = [], [], []
for r in range(m):
for c in range(n):
if g[r][c] == 1 and not seen[r][c]:
cells, threat, w = [], set(), 0
q = deque([(r, c)])
seen[r][c] = True
while q:
x, y = q.popleft()
cells.append((x, y))
for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= nx < m and 0 <= ny < n:
if g[nx][ny] == 0:
threat.add((nx, ny))
w += 1
elif g[nx][ny] == 1 and not seen[nx][ny]:
seen[nx][ny] = True
q.append((nx, ny))
regions.append(cells)
threats.append(threat)
walls.append(w)
if not regions:
break
i = max(range(len(regions)), key=lambda k: len(threats[k]))
if not threats[i]:
break
total += walls[i]
for x, y in regions[i]:
g[x][y] = 2
for k in range(len(regions)):
if k != i:
for x, y in threats[k]:
g[x][y] = 1
return totalFrequently Asked Questions
What is the Contain Virus problem?
Contain Virus simulates an outbreak on a grid: each day you can wall off the single infected region that threatens the most uninfected cells, and then every other region spreads to its neighbors. The task is to return the total number of walls built. It is a long simulation that rewards clean decomposition into "find regions", "pick one", "wall it", and "spread".
How do you solve Contain Virus?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Contain Virus?
Contain Virus is asked at Flipkart. It is a hard difficulty problem.
What are common mistakes on Contain Virus?
- Counting threatened cells instead of walls for the answer. A cell touching the region on two sides needs two walls.
- Choosing the region by wall count. The region to quarantine is the one threatening the most cells.
- Letting quarantined cells spread later. Mark them with a distinct value so they are ignored in future days.
- Spreading while still scanning for regions. Collect everything for the day first, then apply the spread.