Leetcode 749. Contain Virus

Problem Explanation:

In this problem, we have a 2D world where each cell can be either uninfected (represented by 0) or infected (represented by 1). The task is to find the minimum number of walls required to contain the spread of the infection to protect the most uninfected cells.

The infection spreads every night to all neighboring cells in all four directions unless blocked by a wall. Each day, we can build walls around one continuous region (block of infected cells) that threatens the most uninfected cells the following night. One important rule here is that walls are only built on the boundary of two different cells.

Our task is to find the minimum number of walls needed to contain the virus and prevent it from spreading to the most uninfected cells. If the virus spreads to all cells, then we have to return the number of walls used.

Solution Approach:

The solution applies Depth-First-Search (DFS) to find all infected regions and calculate the number of walls required to contain each region. For each day, walls are built around the region that threatens to infect the most uninfected cells. For the remaining regions, the virus will spread to their neighboring uninfected cells. This process continues until no region can cause further infection.

The Region object is used to keep track of the infected cells, noninfected neighboring cells, and the number of walls required to contain the region. The 'infected' and 'noninfected' are stored as a hash of their coordinates, and the hash function is calculated as x * num_of_columns + y

This process is continued until there are no more regions that can cause further infection. If there is such a region, walls are built around the region that will infect the most number of neighbors the following day. The virus is then allowed to spread in the remaining regions.

Solution Explanation:

Let's take an example, and clearly describe how the solution works:

Let's consider the grid:

1
2
3[[0,1,0,0,0,0,0,1],
4 [0,1,0,0,0,0,0,1],
5 [0,0,0,0,0,0,0,1],
6 [0,0,0,0,0,0,0,0]]

In the first round, we find two regions to be infected. The region on the left requires 5 walls to be contained and threatens to infect 4 cells. The region on the right also requires 5 walls to be contained but threatens to infect 6 cells. Therefore, we choose to contain the region on the right with 5 walls, making the total number of walls to be 5.

In the next round, the left region will spread and infect 4 cells, and the grid will be as below:

1
2
3[[0,1,0,0,0,0,1,1],
4 [0,1,0,0,0,0,1,1],
5 [0,0,0,0,0,0,1,1],
6 [0,0,0,0,0,0,0,1]]

There is only one region that's not contained, and it's threatening 4 cells with 5 walls required. Therefore, we use the 5 walls to contain the region on the left. Making the total walls to be 5+5 = 10.

Python Solution

1
2python
3class Solution:
4    def containVirus(self, grid):
5        m, n = len(grid), len(grid[0])
6        def dfs(i, j, visited, cp, wall, area):
7            if (i, j) not in visited:
8                visited.add((i, j))
9                cp.add((i,j))
10                if i > 0: 
11                    if grid[i - 1][j] == 1:
12                        dfs(i - 1, j, visited, cp, wall, area)
13                    elif grid[i - 1][j] == 0:
14                        wall[0] += 1
15                        area.add((i - 1, j))
16                if i < m - 1:
17                    if grid[i + 1][j] == 1:
18                        dfs(i + 1, j, visited, cp, wall, area)
19                    elif grid[i + 1][j] == 0:
20                        wall[0] += 1
21                        area.add((i + 1, j))
22                if j > 0:
23                    if grid[i][j - 1] == 1:
24                        dfs(i, j - 1, visited, cp, wall, area)
25                    elif grid[i][j - 1] == 0:
26                        wall[0] += 1
27                        area.add((i, j - 1))
28                if j < n - 1:
29                    if grid[i][j + 1] == 1:
30                        dfs(i, j + 1, visited, cp, wall, area)
31                    elif grid[i][j + 1] == 0:
32                        wall[0] += 1
33                        area.add((i, j + 1))
34        while True:
35            isolate, walls, perimeter, visited = [], [0] * m * n , [0] * m * n ,set()
36            for i in range(m):
37                for j in range(n):
38                    if grid[i][j] == 1 and (i,j) not in visited:
39                        cp, wall, area = set(), [0], set()
40                        dfs(i, j, visited, cp, wall, area)
41                        isolate.append(cp)
42                        if area:
43                            walls[len(isolate) - 1], perimeter[len(isolate) - 1] = wall[0], len(area)
44            if max(perimeter) == 0: return sum(walls)
45            idx = perimeter.index(max(perimeter))
46            for i, j in isolate[idx]:
47                grid[i][j] = -1
48            for i in range(len(isolate)):
49                if i != idx:
50                    for x, y in isolate[i]:
51                        if x > 0: grid[x - 1][y] = grid[x - 1][y] or grid[x][y]
52                        if x < m - 1: grid[x + 1][y] = grid[x + 1][y] or grid[x][y]
53                        if y > 0: grid[x][y - 1] = grid[x][y - 1] or grid[x][y]
54                        if y < n - 1: grid[x][y + 1] = grid[x][y + 1] or grid[x][y]

Java Solution

1
2java
3class Solution {
4    class cell {
5        int row, col;
6        public cell(int row, int col) {
7            this.row = row;
8            this.col = col;
9        }
10    }
11    int [][]dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
12    int []dx = {0, 1, 1, 1, 0, -1, -1, -1}, dy = {1, 1, 0, -1, -1, -1, 0, 1};
13    public int containVirus(int[][] grid) {
14        int result = 0;
15        while (true) {
16            int walls = processFirst(grid);
17            if (walls == 0) break;
18            result += walls;
19            processSecond(grid);
20        }
21        return result;
22    }
23    int processFirst(int [][]grid) {
24        List<Set<cell>> regions = new ArrayList<>();
25        boolean [][]visited = new boolean[grid.length][grid[0].length];
26        int maxPerimeter = 0, maxIdx = 0, count = 0;
27        for (int i = 0; i < grid.length; i++) {
28            for (int j = 0; j < grid[0].length; j++) {
29                if (grid[i][j] == 1 && !visited[i][j]) {
30                    Set<cell> region = new HashSet<>();
31                    int currPerimeter = dfs(grid, visited, region, i, j);
32                    if (region.size() == 0) continue;
33                    if (currPerimeter > maxPerimeter) {
34                        maxPerimeter = currPerimeter;
35                        maxIdx = count;
36                    }
37                    regions.add(region);
38                    count++;
39                }
40            }
41        }
42        if (regions.size() == 0) return 0;
43        for (cell c : regions.get(maxIdx)) grid[c.row][c.col] = -1;
44        return maxPerimeter;
45    }
46
47    int dfs(int [][]grid, boolean [][]visited, Set<cell> region, int i, int j) {
48        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] <= 0 || visited[i][j]) return 0;
49        visited[i][j] = true;
50        region.add(new cell(i, j));
51        int perimeter = 0;
52        for (int []dir: dirs) {
53            int newX = i + dir[0], newY = j + dir[1];
54            if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 0) perimeter++;
55            perimeter += dfs(grid, visited, region, newX, newY);
56        }
57        return perimeter;
58    }
59
60    void processSecond(int [][]grid) {
61        boolean [][]visited = new boolean[grid.length][grid[0].length];
62        for (int i = 0; i < grid.length; i++) {
63            for (int j = 0; j < grid[0].length; j++) {
64                if (!visited[i][j] && grid[i][j] == 1) dfsForSecond(grid, visited, i, j);
65            }
66        }
67        for (int i = 0; i < grid.length; i++) {
68            for (int j = 0; j < grid[0].length; j++) {
69                if (grid[i][j] > 1) grid[i][j] = 1;
70            }
71        }
72    }
73
74    void dfsForSecond(int [][]grid, boolean [][]visited, int i, int j) {
75        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited[i][j] || grid[i][j] == 0 || grid[i][j] == -1) return;
76        visited[i][j] = true;
77        grid[i][j] = 2;
78        for (int []dir: dirs) {
79            int newX = i + dir[0], newY = j + dir[1];
80            dfsForSecond(grid, visited, newX, newY);
81        }
82    }
83}

JavaScript Solution

1
2javascript
3class Infected {
4  constructor() {
5    this.nodes = new Set();
6    this.perimeter = 0;
7  }
8}
9
10/**
11 * @param {number[][]} grid
12 * @return {number}
13 */
14var containVirus = function(grid) {
15  let walls = 0;
16  while (true) {
17    const { infected, maxInfectedIdx } = findInfected(grid);
18    if (infected.length === 0) break;
19    walls += infected[maxInfectedIdx].perimeter;
20    for (let { r, c } of Array.from(infected[maxInfectedIdx].nodes)) grid[r][c] = -1;
21    spreadVirus(grid, infected, maxInfectedIdx);
22  }
23  
24  return walls;
25};
26
27function spreadVirus(grid, infected, skipIdx) {
28  for (let i = 0; i < infected.length; i++) {
29    if (i === skipIdx) continue;
30    for (let { r, c } of Array.from(infected[i].nodes)) {
31      for (let [dr, dc] of [[-1, 0], [0, 1], [1, 0], [0, -1]]) {
32        const r2 = r + dr;
33        const c2 = c + dc;
34        if (grid[r2] && grid[r2][c2] === 0) grid[r2][c2] = 1;
35      }
36    }
37  }
38}
39
40function findInfected(grid) {
41  const infected = [];
42  const visited = Array(grid.length).fill(0).map(() => Array(grid[0].length).fill(false));
43
44  let maxInfectedIdx = -1;
45  let maxInfectedVal = -1;
46  for (let r = 0; r < grid.length; r++) {
47    for (let c = 0; c < grid[0].length; c++) {
48      if (grid[r][c] === 1 && !visited[r][c]) {
49        const currInfected = new Infected();
50        dfs(grid, r, c, visited, currInfected);
51        infected.push(currInfected);
52        if (currInfected.perimeter > maxInfectedVal) {
53          maxInfectedVal = currInfected.perimeter;
54          maxInfectedIdx = infected.length - 1;
55        }
56      }
57    }
58  }
59  
60  return { infected, maxInfectedIdx };
61}
62
63function dfs(grid, r, c, visited, currInfected) {
64  if (grid[r] === undefined || grid[r][c] === undefined || visited[r][c]) return;
65  
66  visited[r][c] = true;
67  if (grid[r][c] === 1) {
68    currInfected.nodes.add({ r, c });
69    
70    for (let [dr, dc] of [[-1, 0], [0, 1], [1, 0], [0, -1]]) dfs(grid, r+dr, c+dc, visited, currInfected);
71  } else if (grid[r][c] === 0) {
72    currInfected.perimeter++;
73  }
74}

All three solutions implement the same concepts of DFS with minor variations depending on the language features, and they are explained as below:

• Python: The solution starts with defining the size of the grid, and a helper function to perform Depth-First Search (DFS) through different cells. It checks for visited cells, infected cells and calculates the number of walls required for isolation. Then it repeats the process until it finds no region to spread further. If yes, adds the walls required for that region to a total.

• Java: The solution begins with the definition of inner classes for cell representation and direction. The processFirst function calculates the maximum perimeter and updates the grid for the region with the maximum perimeter. The dfs function completes the DFS and returns the required perimeter to contain the infection. The processSecond function causes the virus to spread while updating the grid.

• JavaScript: The JavaScript solution starts with a class definition for 'Infected' and then has three helper functions: containVirus, spreadVirus, and findInfected. It first finds the infected regions, then calculates the walls and finally spreads the virus. It uses Set to keep track of visited cells and avoid repeating DFS for the same cell.

We can see all solutions are effectively using DFS and reciprocating each other in terms of the logic applied. They are containing the virus and spreading it based on the conditions met, and they keep track of the number of walls needed during the process. All these implementations are efficient and solve the problem as expected.