Introduction

In this blog post, we will explore how to solve the LeetCode problem "827" 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

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in grid after applying this operation. An island is a 4-directionally connected group of 1s. Example 1: Input: grid = [[1,0],[0,1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3. Example 2: Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. Example 3: Input: grid = [[1,1],[1,1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4. Constraints: n == grid.length n == grid[i].length 1 <= n <= 500 grid[i][j] is either 0 or 1.

Explanation

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

• Island Labeling: Use Depth-First Search (DFS) to identify and label each connected island with a unique ID. Simultaneously calculate the area (number of cells) of each island.
• Zero Examination: Iterate through all the zero cells in the grid. For each zero cell, examine its four neighboring cells.

• Island Merging: If a zero cell has neighboring islands, calculate the potential island size after converting the zero to one. This size is the sum of the areas of the neighboring islands plus one (for the converted zero cell). Keep track of the maximum island size found so far.

• Runtime Complexity: O(n^2), Storage Complexity: O(n^2)

Code

    def largestIsland(grid):
    n = len(grid)
    island_id = 2  # Start island IDs from 2 (0 and 1 are reserved)
    island_sizes = {}
    max_island = 0

    def dfs(i, j, island_id):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
            return 0
        grid[i][j] = island_id
        size = 1
        size += dfs(i + 1, j, island_id)
        size += dfs(i - 1, j, island_id)
        size += dfs(i, j + 1, island_id)
        size += dfs(i, j - 1, island_id)
        return size

    # 1. Label Islands and calculate sizes
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                size = dfs(i, j, island_id)
                island_sizes[island_id] = size
                max_island = max(max_island, size)
                island_id += 1

    # 2. Find Zeros and merge adjacent islands
    max_island_after_flip = max_island
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                neighbor_islands = set()
                if i > 0 and grid[i - 1][j] != 0:
                    neighbor_islands.add(grid[i - 1][j])
                if i < n - 1 and grid[i + 1][j] != 0:
                    neighbor_islands.add(grid[i + 1][j])
                if j > 0 and grid[i][j - 1] != 0:
                    neighbor_islands.add(grid[i][j - 1])
                if j < n - 1 and grid[i][j + 1] != 0:
                    neighbor_islands.add(grid[i][j + 1])

                total_size = 1  # Start with 1 (for the flipped zero)
                for island in neighbor_islands:
                    total_size += island_sizes.get(island, 0)  # Handle edge cases

                max_island_after_flip = max(max_island_after_flip, total_size)

    return max_island_after_flip