{x}
blog image

Contain Virus

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as an m x n binary grid isInfected, where isInfected[i][j] == 0 represents uninfected cells, and isInfected[i][j] == 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region (i.e., the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night). There will never be a tie.

Return the number of walls used to quarantine all the infected regions. If the world will become fully infected, return the number of walls used.

 

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: There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

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: The region on the left only builds two new walls.

 

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 throughout the described process that will infect strictly more uncontaminated squares in the next round.

Solution Explanation for LeetCode 749: Contain Virus

This problem simulates the spread of a virus on a grid and requires strategically placing walls to contain it. The solution uses Depth-First Search (DFS) to identify infected regions, calculates the number of walls needed, and simulates the virus spread each day.

Algorithm:

  1. Identify Infected Regions: The algorithm iterates through the grid. When it encounters an infected cell (1) that hasn't been visited, it performs a DFS to explore the entire connected component (infected region). During the DFS:

    • It marks visited cells.
    • It stores the coordinates of all cells in the region (areas).
    • It counts the number of uninfected neighbors (c). These are the cells that will be infected the next day unless walls are built.
    • It keeps track of the coordinates of uninfected neighbors (boundaries).

  2. Find the Most Threatening Region: After identifying all regions, the algorithm determines the region that threatens the most uninfected cells (the region with the largest boundaries).

  3. Build Walls and Simulate Spread: Walls are built around the most threatening region (c[idx] walls are built). The infected cells in that region are marked as quarantined (-1). Then, the algorithm simulates the virus spread for the remaining regions. For each remaining region, the algorithm checks the uninfected neighbors of its infected cells. If an uninfected neighbor exists, it becomes infected (1).

  4. Repeat: Steps 1-3 are repeated until there are no more infected regions left. The total number of walls used is returned.

Time Complexity Analysis:

  • The DFS in step 1 visits each cell at most once. Therefore, the time complexity of the DFS is O(m*n), where 'm' and 'n' are the dimensions of the grid.
  • Step 2 takes O(k), where 'k' is the number of infected regions. In the worst case, k could be O(m*n).
  • The loop in step 3 iterates at most m*n times (since that's the maximum number of infected cells), and the operations within the loop are O(1).
  • The whole process repeats until no infected regions are left, and in the worst case, this could happen up to O(m*n) times.

Therefore, the overall time complexity is O(mn * k), which can be O((mn)^2) in the worst case. However, in practice, it's usually much less due to the nature of the virus spread.

Space Complexity Analysis:

  • vis: O(m*n) space to track visited cells.
  • areas, c, boundaries: The space used by these lists is proportional to the number of infected regions, which could be at most O(m*n).
  • The recursive stack in DFS could also use up to O(m*n) space in the worst case.

So the total space complexity is O(m*n).

Code in Different Languages:

The code provided earlier in the response demonstrates the solution in Python, Java, C++, and Go. Each implementation follows the same core algorithm, with minor syntax differences due to language-specific features. The data structures used are chosen to efficiently handle the operations required for the algorithm. For example, sets are used for boundaries in Python and C++ for efficient membership checking. In the Go solution, maps are used instead which gives the same functionality. The Java solution uses a HashSet for the same purpose. The usage of lists/arrays and sets/maps allows for efficient operations when dealing with coordinates and sets of coordinates.