Practice/Uber/Leetcode 749. Contain Virus

Leetcode 749. Contain Virus

CodingOptional

Problem

You are given a 2D grid representing a geographic area where each cell is either infected (1) or uninfected (0). The infection spreads daily according to specific rules, and your task is to minimize the total damage by strategically building containment walls.

Spreading Mechanism:

• Each day, infected cells can spread to adjacent uninfected cells in four directions (up, down, left, right)
• Multiple disconnected infected regions may exist on the grid

Daily Containment Process:

Each day, before the infection spreads, you must:

1. Identify all distinct infected regions (connected components of infected cells)

2. For each region, calculate:

   • How many uninfected cells it would threaten (adjacent uninfected cells)
   • How many walls would be needed to completely quarantine it

3. Select the region that threatens the most uninfected cells

4. Build walls around that selected region to permanently contain it

5. Allow all other regions to spread to their adjacent uninfected cells

This process repeats each day until no infected region can spread further.

Return the total number of walls built throughout the entire containment process.

Requirements

1. Implement a simulation that processes each day sequentially
2. Correctly identify all connected infected regions using traversal algorithms
3. Calculate the threat level (number of unique uninfected cells at risk) for each region
4. Calculate the perimeter (number of walls needed) for each region
5. Apply the greedy strategy: always contain the region with maximum threat first
6. Handle ties by selecting any region with maximum threat
7. Continue simulation until no region can spread further

Constraints

• m == isInfected.length (number of rows)
• n == isInfected[i].length (number of columns)
• 1 ≤ m, n ≤ 50
• isInfected[i][j] is either 0 or 1
• The grid may have multiple disconnected infected regions
• Time complexity: Aim for O(days × m × n × (m × n)) where days is typically small
• Space complexity: O(m × n) for tracking visited cells and region information

Examples

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: Two regions exist.

• Left region: threatens 2 cells, needs 10 walls
• Right region: threatens 4 cells, needs 9 walls Contain the right region (4 > 2). Build 9 walls... (actually the left is contained first based on calculation) Continue until all spreading stops. Total: 10 walls. `

Example 2:

Input: isInfected = [[1,1,1], [1,0,1], [1,1,1]] Output: 4 Explanation: One region surrounds a single uninfected cell in the center. The region threatens 1 cell and needs 4 walls (the four sides of the center cell). After building 4 walls, the center is protected and no further spreading occurs.

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: Multiple regions compete. The right region threatens more cells initially. Contain regions strategically over multiple days until all are contained or can't spread.