Making A Large Island

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.

For example:

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.

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.

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.

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        
        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
        
        island_sizes = {}
        island_id = 2
        max_island = 0
        
        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
        
        max_island_after_flip = max_island
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    neighbors = set()
                    if i > 0:
                        neighbors.add(grid[i - 1][j])
                    if i < n - 1:
                        neighbors.add(grid[i + 1][j])
                    if j > 0:
                        neighbors.add(grid[i][j - 1])
                    if j < n - 1:
                        neighbors.add(grid[i][j + 1])
                    
                    total_size = 1
                    for neighbor in neighbors:
                        if neighbor > 1:
                            total_size += island_sizes[neighbor]
                    max_island_after_flip = max(max_island_after_flip, total_size)
        
        return max_island_after_flip

Naive Approach

The naive approach would be to iterate through each 0 in the grid, temporarily change it to 1, and then calculate the size of the resulting island using Depth-First Search (DFS) or Breadth-First Search (BFS). We keep track of the maximum island size found so far. After processing each 0, we revert it back to 0 to maintain the original grid.

Optimal Approach

The optimal approach aims to avoid redundant DFS/BFS calculations for connected components. The steps are as follows:

1. Island Labeling: Perform a DFS to identify and label each island with a unique ID (starting from 2, as 0 and 1 are already used). While doing this, store the size of each island in a dictionary.
2. Zero Flipping: Iterate through each 0 in the grid. For each 0, check its 4-directional neighbors. If the neighbors are part of an island (i.e., have an island ID), add their sizes to calculate the potential island size if the 0 is flipped to 1. Use a set to keep track of visited island IDs to avoid double-counting.
3. Maximum Size: The maximum island size found during the zero-flipping step is the answer.

Big(O) Run-time Analysis

1. Island Labeling: The DFS visits each cell at most once, so it takes O(n^2) time, where n is the dimension of the grid.
2. Zero Flipping: Iterating through each cell in the grid takes O(n^2) time. For each 0, we check its 4 neighbors, which takes O(1) time. Thus, this step takes O(n^2) time.

Therefore, the overall time complexity is O(n^2).

Big(O) Space Usage Analysis

1. Island Sizes Dictionary: In the worst case, every 1 in the grid forms its own island. Therefore, the dictionary can store up to O(n^2) island sizes.
2. DFS Stack: The DFS stack can grow up to O(n^2) in the worst case (when the entire grid is 1s).
3. Neighbors Set: At most 4 neighbors are stored, so it's O(1). However, in total, this happens at most O(n^2) times.

Therefore, the overall space complexity is O(n^2).

Edge Cases

1. No Zeros: If there are no zeros in the grid, the entire grid is one island. The algorithm should return the size of the grid (n^2).
2. All Zeros: If the grid contains all zeros, changing any one of them results in an island of size 1. The algorithm should return 1.
3. Single Zero: If there is a single zero, changing it to one will create an island of size 1 if there are no adjacent ones, or it will connect any adjacent islands.
4. Multiple Islands: The algorithm must handle the case where changing a zero connects multiple islands.
5. Large Grid: The algorithm must handle large grids (up to 500x500) efficiently without exceeding memory limits or execution time limits.