Introduction

In this blog post, we will explore how to solve the LeetCode problem "749" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the solution approach, followed by the code:

• Identify Infected Regions: Use Depth-First Search (DFS) to find all distinct infected regions in the grid.
• Prioritize Quarantine: For each region, calculate the number of uninfected cells it threatens. Quarantine the region that threatens the most uninfected cells.

• Install Walls: Count the walls needed to isolate the chosen region. Update the grid to mark the region as quarantined (e.g., change the value to -1 or another distinct value). Repeat until no more regions can spread.

• Runtime Complexity: O(m*n), where m and n are the dimensions of the grid.

• Storage Complexity: O(m*n) due to the recursion depth of DFS and potential storage of visited cells.

Code

    def containVirus(isInfected):
    """
    Calculates the minimum number of walls needed to contain the virus spread.

    Args:
        isInfected: A list of lists representing the infected grid.

    Returns:
        The total number of walls used.
    """

    m = len(isInfected)
    n = len(isInfected[0])
    total_walls = 0

    def dfs(i, j, region_id, regions, visited):
        """
        Performs Depth-First Search to identify and label infected regions.

        Args:
            i: Row index.
            j: Column index.
            region_id: The ID of the current region.
            regions: Dictionary to store region information (threatened cells, walls).
            visited: Set to keep track of visited cells.
        """
        if i < 0 or i >= m or j < 0 or j >= n or (i, j) in visited or isInfected[i][j] != 1:
            return

        visited.add((i, j))
        regions[region_id]["cells"].add((i, j))

        # Explore neighbors
        dfs(i + 1, j, region_id, regions, visited)
        dfs(i - 1, j, region_id, regions, visited)
        dfs(i, j + 1, region_id, regions, visited)
        dfs(i, j - 1, region_id, regions, visited)

    def calculate_threat(region, grid):
        """
        Calculates the number of uninfected cells a region threatens, and the walls needed.

        Args:
            region: Set of infected cell coordinates in the region.
            grid: The infected grid.

        Returns:
            A tuple: (threatened cells, walls needed)
        """
        threatened = set()
        walls = 0
        for r, c in region:
            neighbors = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
            for nr, nc in neighbors:
                if 0 <= nr < m and 0 <= nc < n:
                    if grid[nr][nc] == 0:
                        threatened.add((nr, nc))
                        walls += 1
                    elif grid[nr][nc] == 1:
                        walls += 1 # wall between two infected cells in different regions.
        return threatened, walls

    while True:
        regions = {}
        region_id = 0
        visited = set()
        for i in range(m):
            for j in range(n):
                if isInfected[i][j] == 1 and (i, j) not in visited:
                    regions[region_id] = {"cells": set(), "threatened": set(), "walls": 0}
                    dfs(i, j, region_id, regions, visited)
                    region_id += 1

        if not regions:
            break  # No more infected regions

        # Calculate threat for each region
        for region_id, region_data in regions.items():
            threatened, walls = calculate_threat(region_data["cells"], isInfected)
            regions[region_id]["threatened"] = threatened
            regions[region_id]["walls"] = walls

        # Find the region that threatens the most uninfected cells
        max_threat = 0
        max_threat_region = -1
        for region_id, region_data in regions.items():
            if len(region_data["threatened"]) > max_threat:
                max_threat = len(region_data["threatened"])
                max_threat_region = region_id

        # If no region threatens any uninfected cells, we're done
        if max_threat_region == -1:
            break

        # Quarantine the most threatening region
        total_walls += regions[max_threat_region]["walls"]

        # Mark quarantined region as contained (e.g., -1)
        for r, c in regions[max_threat_region]["cells"]:
            isInfected[r][c] = -1

        # Spread the virus in other regions (that weren't quarantined)
        new_infected = set()
        for region_id, region_data in regions.items():
            if region_id != max_threat_region:
                for r, c in region_data["threatened"]:
                    new_infected.add((r, c))
        for r, c in new_infected:
            isInfected[r][c] = 1

    return total_walls