Contain Virus — Solution in Python, Java & C++
Contain Virus solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Contain Virus is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Simulation
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A virus is spreading over an m x n grid isInfected, where 1 marks an infected cell and 0 a clean one. Infected cells that touch up, down, left or right form a region.
You can build walls on the boundary between two adjacent cells. Each day you have resources to wall off exactly one region: the region that threatens the most clean cells (the number of distinct clean cells adjacent to it). You build a wall on every shared side between that region and a clean cell, and that region never spreads again. It is guaranteed that this region is always unique.
Then, at night, every other region spreads to all clean cells adjacent to it.
Repeat until no region threatens any clean cell. Return the total number of walls built. (If the whole grid becomes infected, the process simply stops.)
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: Day 1 walls the right-hand region (5 threatened cells, 5 walls) while the left one spreads; day 2 walls the left region with 5 more.
Example 2
Input: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
Output: 4
Explanation: One region threatens only the centre cell, but four infected cells border it.
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: Walls between infected cells and the clean centre count too.
Constraints
m == isInfected.lengthn == isInfected[i].length1 <= m, n <= 50isInfected[i][j] is 0 or 1on every day there is a unique region threatening the most clean cells
Hints for Contain Virus
Hint 1
Simulate day by day. Each day, find all infected regions with a flood fill.
Hint 2
For each region record two numbers: the distinct clean cells it touches (to choose the region) and the number of walls — every (infected cell, clean neighbour) pair, counted with multiplicity.
Hint 3
Wall off the region with the most threatened cells by marking its cells as dead (say
-1), then infect every threatened cell of every other region. Stop when the largest threat is zero.
How to solve Contain Virus
There is nothing to optimise — the rules fix which region is walled each day — so the task is a careful simulation. The subtlety is that two different counts are involved: threatened cells (distinct) decide the choice, walls (per shared side) decide the cost.
Approach
- Loop: flood-fill every region of
1cells. For each, collect the set of adjacent0cells (frontier) and countwalls, the number of (cell, clean neighbour) pairs. - If there is no region, or the largest frontier is empty, stop and return the total.
- Pick the region with the largest frontier; add its
wallsto the total and set its cells to-1so they are neither counted nor spread again. - For every other region, set each frontier cell to
1.
Why it works
The day's process is deterministic given the grid, and the problem guarantees the chosen region is unique, so the simulation reproduces exactly the walls that get built. Marking contained cells -1 keeps them out of future flood fills and keeps them from being reinfected, matching a region that has been sealed in.
Complexity
- Time —
O((m · n)^(4/3)) - Space —
O(m · n)
Pitfalls
- A clean cell touched by a region on two sides counts once toward the threat but needs two walls.
- Spread only after choosing and containing, and spread every other region simultaneously — a newly infected cell does not spread again that same night.
- Contained cells must not be treated as infected or clean afterwards.
Reference solution
Python
from typing import List
def containVirus(isInfected: List[List[int]]) -> int:
g = [row[:] for row in isInfected]
m, n = len(g), len(g[0])
total = 0
while True:
seen = [[False] * n for _ in range(m)]
regions, fronts, walls = [], [], []
for i in range(m):
for j in range(n):
if g[i][j] != 1 or seen[i][j]:
continue
cells, front, w = [], set(), 0
seen[i][j] = True
stack = [(i, j)]
while stack:
r, c = stack.pop()
cells.append((r, c))
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n:
if g[nr][nc] == 0:
front.add((nr, nc))
w += 1
elif g[nr][nc] == 1 and not seen[nr][nc]:
seen[nr][nc] = True
stack.append((nr, nc))
regions.append(cells)
fronts.append(front)
walls.append(w)
if not regions:
break
best = max(range(len(regions)), key=lambda k: len(fronts[k]))
if not fronts[best]:
break
total += walls[best]
for r, c in regions[best]:
g[r][c] = -1
for k in range(len(regions)):
if k != best:
for r, c in fronts[k]:
g[r][c] = 1
return totalJava
public static int containVirus(int[][] isInfected) {
int m = isInfected.length, n = isInfected[0].length, total = 0, token = 0;
int[] g = new int[m * n], stamp = new int[m * n], rid = new int[m * n], stack = new int[m * n];
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) g[i * n + j] = isInfected[i][j];
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
while (true) {
Arrays.fill(rid, -1);
List<List<Integer>> fronts = new ArrayList<>();
List<Integer> walls = new ArrayList<>();
for (int s = 0; s < m * n; s++) {
if (g[s] != 1 || rid[s] != -1) continue;
int id = fronts.size(), w = 0, top = 0;
List<Integer> front = new ArrayList<>();
token++;
rid[s] = id;
stack[top++] = s;
while (top > 0) {
int cur = stack[--top], r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int t = nr * n + nc;
if (g[t] == 0) { w++; if (stamp[t] != token) { stamp[t] = token; front.add(t); } }
else if (g[t] == 1 && rid[t] == -1) { rid[t] = id; stack[top++] = t; }
}
}
fronts.add(front);
walls.add(w);
}
if (fronts.isEmpty()) break;
int best = 0;
for (int q = 1; q < fronts.size(); q++) if (fronts.get(q).size() > fronts.get(best).size()) best = q;
if (fronts.get(best).isEmpty()) break;
total += walls.get(best);
for (int y = 0; y < m * n; y++) if (rid[y] == best) g[y] = -1;
for (int z = 0; z < fronts.size(); z++) {
if (z == best) continue;
for (int t : fronts.get(z)) g[t] = 1;
}
}
return total;
}C++
int containVirus(vector<vector<int>>& isInfected) {
int m = isInfected.size(), n = isInfected[0].size(), total = 0, token = 0;
vector<int> g(m * n), stamp(m * n, 0), rid(m * n);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) g[i * n + j] = isInfected[i][j];
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
while (true) {
fill(rid.begin(), rid.end(), -1);
vector<vector<int>> fronts;
vector<int> walls;
for (int s = 0; s < m * n; s++) {
if (g[s] != 1 || rid[s] != -1) continue;
int id = fronts.size(), w = 0;
vector<int> front, st{s};
token++;
rid[s] = id;
while (!st.empty()) {
int cur = st.back(); st.pop_back();
int r = cur / n, c = cur % n;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
int t = nr * n + nc;
if (g[t] == 0) { w++; if (stamp[t] != token) { stamp[t] = token; front.push_back(t); } }
else if (g[t] == 1 && rid[t] == -1) { rid[t] = id; st.push_back(t); }
}
}
fronts.push_back(front);
walls.push_back(w);
}
if (fronts.empty()) break;
int best = 0;
for (int q = 1; q < (int)fronts.size(); q++) if (fronts[q].size() > fronts[best].size()) best = q;
if (fronts[best].empty()) break;
total += walls[best];
for (int y = 0; y < m * n; y++) if (rid[y] == best) g[y] = -1;
for (int z = 0; z < (int)fronts.size(); z++) {
if (z == best) continue;
for (int t : fronts[z]) g[t] = 1;
}
}
return total;
}JavaScript
var containVirus = function(isInfected) {
var m = isInfected.length, n = isInfected[0].length, total = 0, token = 0;
var g = [], stamp = [];
for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) { g.push(isInfected[i][j]); stamp.push(0); }
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
for (;;) {
var rid = [], fronts = [], walls = [];
for (var x = 0; x < m * n; x++) rid.push(-1);
for (var s = 0; s < m * n; s++) {
if (g[s] !== 1 || rid[s] !== -1) continue;
var id = fronts.length, front = [], w = 0, stack = [s];
token++;
rid[s] = id;
while (stack.length) {
var cur = stack.pop(), r = Math.floor(cur / n), c = cur % n;
for (var k = 0; k < 4; k++) {
var nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
var t = nr * n + nc;
if (g[t] === 0) { w++; if (stamp[t] !== token) { stamp[t] = token; front.push(t); } }
else if (g[t] === 1 && rid[t] === -1) { rid[t] = id; stack.push(t); }
}
}
fronts.push(front);
walls.push(w);
}
if (fronts.length === 0) break;
var best = 0;
for (var q = 1; q < fronts.length; q++) if (fronts[q].length > fronts[best].length) best = q;
if (fronts[best].length === 0) break;
total += walls[best];
for (var y = 0; y < m * n; y++) if (rid[y] === best) g[y] = -1;
for (var z = 0; z < fronts.length; z++) {
if (z === best) continue;
for (var f = 0; f < fronts[z].length; f++) g[fronts[z][f]] = 1;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)