Contain Virus

Hard
1686.

Contain Virus

Contain Virus is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Microsoft interviews.

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.length
  • n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] is 0 or 1
  • on every day there is a unique region threatening the most clean cells
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} isInfected
 * @return {number}
 */
var containVirus = function(isInfected) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] is 0 or 1
  • on every day there is a unique region threatening the most clean cells

Hints for Contain Virus

  1. Hint 1

    Simulate day by day. Each day, find all infected regions with a flood fill.

  2. 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.

  3. 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

  1. Loop: flood-fill every region of 1 cells. For each, collect the set of adjacent 0 cells (frontier) and count walls, the number of (cell, clean neighbour) pairs.
  2. If there is no region, or the largest frontier is empty, stop and return the total.
  3. Pick the region with the largest frontier; add its walls to the total and set its cells to -1 so they are neither counted nor spread again.
  4. 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 total

Java

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)