Contain Virus

Hard Graphs Matrix Graphs Original on LeetCode

Reported atFlipkart

Contain Virus is a hard graphs problem solved with the matrix graphs pattern. The best approach, optimal (one flood fill per region per day), runs in O(D · m · n), D = number of days time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (rescan the grid per region) up.

Problem

A virus is spreading over an m x n grid isInfected, where 1 marks an infected cell and 0 a healthy one. Every night, each group of connected infected cells (connected up, down, left or right) infects all healthy cells next to it, unless a wall stops it.

Each day you have enough resources to build walls around one region only: the region that would infect the largest number of healthy cells the following night (this region is always unique). A wall is placed on each shared edge between that region and a healthy neighbouring cell, so a healthy cell bordering the region on two sides needs two walls. Once walled, the region never spreads again. All other regions then spread for the night.

Repeat until no region can infect anything (either everything is contained or the virus has taken every reachable cell). Return the total number of walls built.

Examples

Example 1

Input
isInfected = [[0, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0]]
Output
11
Why
Day 1: the left region threatens 5 cells and the right one 4, so the left one is walled with 5 walls while the right one spreads. Day 2: the grown right region is the only one left and needs 6 walls. 5 + 6 = 11.

Example 2

Input
isInfected = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output
4
Why
The ring threatens only the centre cell; it touches the ring on 4 sides, so 4 walls are built.

Example 3

Input
isInfected = [[1, 1], [1, 1]]
Output
0
Why
There is no healthy cell to protect, so no wall is ever needed.

Constraints

  • m == isInfected.length, n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] is 0 or 1.
  • On every day the region that threatens the most healthy cells is unique.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (rescan the grid per region)O(R · m · n) per dayO(m · n)
Optimal (one flood fill per region per day)O(D · m · n), D = number of daysO(m · n)

1Brute force (rescan the grid per region)

TimeO(R · m · n) per dayEvery one of the R regions triggers a full scan of the m × n grid each day.
SpaceO(m · n)The label grid and the list of newly infected cells.

Simulate the days. Each day, label every active region with a flood fill. Then, for each region separately, scan the whole grid to count the healthy cells next to it and the walls it needs. Wall the most dangerous region, and spread the rest by scanning the grid once more.

  1. Flood fill to give every active infected cell a region label 0..R-1; stop if there is none.
  2. For every region r: scan all cells; a healthy cell with a neighbour labelled r is threatened; each (cell labelled r, healthy neighbour) pair is a wall.
  3. Pick the region with the most threatened cells; if that is 0, stop. Add its walls to the answer and set its cells to -1.
  4. Every healthy cell with a neighbour in another active region becomes infected (collect them first, then apply).
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public int containVirus(int[][] isInfected) {
        int m = isInfected.length, n = isInfected[0].length, total = 0;
        while (true) {
            int[][] label = new int[m][n];
            for (int[] row : label) Arrays.fill(row, -1);
            int regions = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] == 1 && label[i][j] == -1) fill(isInfected, label, i, j, regions++);
                }
            }
            if (regions == 0) break;
            int best = -1, bestThreat = 0, bestWalls = 0;
            for (int r = 0; r < regions; r++) {
                int threat = 0, walls = 0;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (isInfected[i][j] != 0) continue;
                        boolean touched = false;
                        for (int[] d : DIRS) {
                            int x = i + d[0], y = j + d[1];
                            if (x >= 0 && x < m && y >= 0 && y < n && label[x][y] == r) { touched = true; walls++; }
                        }
                        if (touched) threat++;
                    }
                }
                if (threat > bestThreat) { bestThreat = threat; best = r; bestWalls = walls; }
            }
            if (best == -1) break;
            total += bestWalls;
            List<int[]> spread = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (label[i][j] == best) isInfected[i][j] = -1;
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] != 0) continue;
                    for (int[] d : DIRS) {
                        int x = i + d[0], y = j + d[1];
                        if (x >= 0 && x < m && y >= 0 && y < n && label[x][y] != -1 && label[x][y] != best) {
                            spread.add(new int[] { i, j });
                            break;
                        }
                    }
                }
            }
            for (int[] c : spread) isInfected[c[0]][c[1]] = 1;
        }
        return total;
    }

    private void fill(int[][] g, int[][] label, int si, int sj, int id) {
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[] { si, sj });
        label[si][sj] = id;
        while (!stack.isEmpty()) {
            int[] c = stack.pop();
            for (int[] d : DIRS) {
                int x = c[0] + d[0], y = c[1] + d[1];
                if (x >= 0 && x < g.length && y >= 0 && y < g[0].length && g[x][y] == 1 && label[x][y] == -1) {
                    label[x][y] = id;
                    stack.push(new int[] { x, y });
                }
            }
        }
    }
}

2Optimal (one flood fill per region per day)

TimeO(D · m · n), D = number of daysEach day is a single O(m · n) pass over the grid. Regions only merge and one is removed per day, so D is at most the initial number of regions.
SpaceO(m · n)The visited grid and the per-region cell lists and threatened sets.

Gather everything about a region during its own flood fill: while exploring an active region, every healthy neighbour goes into that region's threatened set and every (infected cell, healthy neighbour) edge adds one wall. One pass over the grid then gives all regions with their threat sets and wall counts. Wall the region with the largest set, mark its cells -1, and infect the threatened sets of all other regions.

  1. Each day, flood fill every unvisited active cell (value 1). For its region record the cells, the set of threatened healthy cells, and the wall count.
  2. If there are no regions, or the largest threatened set is empty, stop.
  3. Add the walls of the region with the largest threatened set to the answer and set its cells to -1.
  4. For every other region set all its threatened cells to 1. Repeat.
class Solution {
    private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public int containVirus(int[][] isInfected) {
        int m = isInfected.length, n = isInfected[0].length, total = 0;
        while (true) {
            boolean[][] seen = new boolean[m][n];
            List<List<int[]>> regions = new ArrayList<>();
            List<Set<Integer>> threats = new ArrayList<>();
            List<Integer> walls = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isInfected[i][j] != 1 || seen[i][j]) continue;
                    List<int[]> cells = new ArrayList<>();
                    Set<Integer> threat = new HashSet<>();
                    int w = 0;
                    Deque<int[]> stack = new ArrayDeque<>();
                    stack.push(new int[] { i, j });
                    seen[i][j] = true;
                    while (!stack.isEmpty()) {
                        int[] c = stack.pop();
                        cells.add(c);
                        for (int[] d : DIRS) {
                            int x = c[0] + d[0], y = c[1] + d[1];
                            if (x < 0 || x >= m || y < 0 || y >= n) continue;
                            if (isInfected[x][y] == 1 && !seen[x][y]) {
                                seen[x][y] = true;
                                stack.push(new int[] { x, y });
                            } else if (isInfected[x][y] == 0) {
                                threat.add(x * n + y);
                                w++;
                            }
                        }
                    }
                    regions.add(cells);
                    threats.add(threat);
                    walls.add(w);
                }
            }
            if (regions.isEmpty()) break;
            int best = 0;
            for (int r = 1; r < regions.size(); r++) {
                if (threats.get(r).size() > threats.get(best).size()) best = r;
            }
            if (threats.get(best).isEmpty()) break;
            total += walls.get(best);
            for (int r = 0; r < regions.size(); r++) {
                if (r == best) {
                    for (int[] c : regions.get(r)) isInfected[c[0]][c[1]] = -1;
                } else {
                    for (int code : threats.get(r)) isInfected[code / n][code % n] = 1;
                }
            }
        }
        return total;
    }
}

Edge cases to test

  • No infected cell at all, or no healthy cell at all (answer 0)
  • A healthy cell touched by one region on several sides: it counts once as threatened but each side needs its own wall
  • Regions that merge after spreading and must then be treated as one region
  • The virus filling the whole grid before every region is contained
  • A single row or a single column

Hints

Hint 1

Simulate day by day. Each day you need every infected region (connected component of active 1s), the set of healthy cells it threatens, and the number of walls it would need.

Hint 2

Threatened cells are a set (a cell touched twice counts once), but walls are counted per (infected cell, healthy neighbour) edge.

Hint 3

Mark the walled region as permanently inactive (for example with -1), then let every other region infect its threatened cells. Stop when no region threatens anything.

FAQ

What is the best time complexity for Contain Virus?

Optimal (one flood fill per region per day) runs in O(D · m · n), D = number of days time and O(m · n) extra space. Each day is a single O(m · n) pass over the grid. Regions only merge and one is removed per day, so D is at most the initial number of regions.

Which pattern does Contain Virus use?

It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Number of Distinct Islands.

Is there a brute force solution for Contain Virus?

Yes. Brute force (rescan the grid per region) takes O(R · m · n) per day time and O(m · n) space. Simulate the days.

Which edge cases should I test for Contain Virus?

No infected cell at all, or no healthy cell at all (answer 0); A healthy cell touched by one region on several sides: it counts once as threatened but each side needs its own wall; Regions that merge after spreading and must then be treated as one region; The virus filling the whole grid before every region is contained; A single row or a single column.