749. Contain Virus
Asked at Flipkart
Difficulty
Hard
Time
O((m * n)^(4/3))
Space
O(m * n)
Pattern
Array
Companies
1
Problem
You are given an m x n grid called isInfected. A cell with value 1 holds the virus, and a cell with value 0 is healthy. The virus spreads every night: each infected cell infects all of its 4-directional neighbors, unless a wall blocks that shared edge.
You may build walls, but only around one infected region per day. A region is a group of infected cells connected up/down/left/right. You must pick the region that would infect the most healthy cells on the next night (the problem guarantees there is never a tie). Building a wall costs one wall per infected-to-healthy edge, so a single healthy cell touching the region on two sides costs two walls.
After you wall off the chosen region, all other regions spread to their healthy neighbors. Cells inside a walled region never spread again. Repeat this each day until no region can infect anything new. Return the total number of walls you built. If the whole grid ends up infected, return the walls used so far.
Two regions, one walled per day
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 that will infect strictly more uncontaminated squares in the next round.
Examples
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]]10isInfected = [[1,1,1],[1,0,1],[1,1,1]]4isInfected = [[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]]13Asked At
1 companies| 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).
Find, pick, wall, spread
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
O((m * n)^(4/3)) timefrom 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 runs in O((m * n)^(4/3)) time and O(m * n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.