Making A Large Island - Leetcode Solution

The Making A Large Island problem on LeetCode is a medium-level problem in which we are given a 2D matrix of 0s and 1s representing an island, where 0 represents water and 1 represents land. The goal is to find the maximum area of an island by changing at most one 0 to 1.

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the island and find the area of each connected component (island). We can keep track of the areas of each connected component using a dictionary. Once we have the areas of all connected components, we can iterate over each 0 in the matrix and check if flipping that 0 to 1 will create a larger island. We can then return the maximum area of the island.

Here is a step-by-step approach to solve the problem:

1. Create a dictionary to store the area of each connected component.

2. Use DFS to traverse the island and find the area of each connected component. For this, we can start at each 1 in the matrix and recursively visit all its neighbors (up, down, left, right) that are also 1s. We can mark each visited cell as -1 to avoid revisiting it. While traversing each connected component, we can add its area to the dictionary.

3. Iterate over each 0 in the matrix and check if flipping that 0 to 1 will create a larger island. For this, we can check the area of each connected component that is adjacent to the 0. We can do this by checking the values of its neighboring cells (up, down, left, right) that are not marked as -1. If we find a neighboring cell with a value of 1, we can add its area to the area of the current connected component. If the resulting area is greater than the maximum area seen so far, we update the maximum area.

4. Return the maximum area of the island.

Here is the Python implementation of the above approach:

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        
        # dictionary to store the area of each connected component
        area_dict = {}
        max_area = 0
        
        # DFS to traverse the island and find the area of each connected component
        def dfs(i, j, area):
            # check if current cell is within bounds and is a land cell
            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]==1:
                # mark cell as visited
                grid[i][j] = -1
                # add cell to current connected component
                area += 1
                # recursive DFS to visit all neighboring land cells
                area = dfs(i-1, j, area)  # up
                area = dfs(i+1, j, area)  # down
                area = dfs(i, j-1, area)  # left
                area = dfs(i, j+1, area)  # right
            return area
        
        # iterate over each cell of the matrix
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    # perform DFS to find the area of the connected component
                    area = dfs(i, j, 0)
                    # add area to dictionary
                    area_dict[(i,j)] = area
                    # update maximum area seen so far
                    max_area = max(max_area, area)
        
        # iterate over each 0 in the matrix and check if flipping it to 1 creates a larger island
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    # check area of each adjacent connected component
                    neighbors = set()
                    for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                        if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!=-1:
                            neighbors.add((x,y))
                    # calculate total area if we flip current 0 to 1
                    area = 1
                    for neighbor in neighbors:
                        area += area_dict.get(neighbor, 0)
                    # update maximum area seen so far
                    max_area = max(max_area, area)
        
        return max_area

The time complexity of the above algorithm is O(n^2) for iterating over each cell of the matrix and performing DFS for each connected component. The space complexity is also O(n^2) for storing the area of each connected component in a dictionary.

1