Leetcode 827. Making A Large Island

Let's understand what we're being asked to do. We have an n×n binary grid where each cell is either 0 (water) or 1 (land). An island is a group of 1s connected horizontally or vertically (4-directional).

For example, in the grid [[1,0],[0,1]], there are two separate islands (top-left and bottom-right), each of size 1. In [[1,1],[1,0]], there's one island of size 3 (the three connected 1s).

The twist: We can flip at most one 0 to 1. Our goal is to find the largest possible island size after this optional flip.

Key constraint: The grid is n×n (square), and 1 <= n <= 500.

Edge cases to consider: What if the grid is already all 1s? (can't flip anything, return n*n). What if flipping a 0 connects multiple separate islands? What if the grid is all 0s? (flip one 0 to get island of size 1).

For each 0 cell in the grid, temporarily flip it to 1, then run a DFS/BFS to compute the size of the resulting island at that position. Track the maximum island size found across all flips. This approach is straightforward but inefficient because we recompute island sizes from scratch for every single 0 cell, leading to repeated work.

def largest_island_brute_force(grid):
    """
    Brute force: For each 0, flip it to 1 and compute island size via DFS.
    Track the maximum island size found across all flips.
    """
    if not grid or not grid[0]:
        return 0
    
    n = len(grid)
    max_island_size = 0
    
    def dfs(r, c, visited):
        # DFS to compute island size starting from (r, c)
        if r < 0 or r >= n or c < 0 or c >= n:
            return 0
        if grid[r][c] == 0 or (r, c) in visited:
            return 0
        
        visited.add((r, c))
        size = 1
        
        # Explore all 4 directions
        size += dfs(r + 1, c, visited)
        size += dfs(r, c + 1, visited)
        size += dfs(r - 1, c, visited)
        size += dfs(r, c - 1, visited)
        
        return size
    
    # Check if grid is already all ones (edge case)
    has_zero = False
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                has_zero = True
                break
        if has_zero:
            break
    
    if not has_zero:
        # All ones - return total grid size
        return n * n
    
    # Try flipping each 0 to 1 and compute resulting island size
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                # Temporarily flip this 0 to 1
                grid[i][j] = 1
                
                # Compute island size at this position using DFS
                visited = set()
                island_size = dfs(i, j, visited)
                
                # Track maximum island size
                max_island_size = max(max_island_size, island_size)
                
                # Flip back to 0 for next iteration
                grid[i][j] = 0
    
    return max_island_size

When we flip a 0 to 1, we're potentially merging multiple existing islands that are adjacent to that 0.

For example, if a 0 is surrounded by three different islands, flipping it would connect all three into one giant island. The key insight is: we need to know the size of each existing island and which islands are neighbors of each 0.

If we can label each island with a unique ID and store its size, then for any 0 cell, we can look at its 4 neighbors, identify which distinct islands touch it, and calculate: 1 + sum of sizes of distinct neighboring islands.

This transforms the problem from 'try flipping every 0 and recompute' (expensive!) to 'precompute island info once, then check each 0 in constant time' (efficient!).

Imagine coloring each island a different color (red, blue, green, etc.) and writing its size on each cell.

Now when you look at a water cell (0), you can see which colored islands touch it. If it touches red (size 5), blue (size 3), and green (size 2), flipping this water cell would create an island of size 1 + 5 + 3 + 2 = 11.

The 'coloring' step is about identifying connected components, and the 'checking water cells' step is about merging distinct neighbors.

First, label each connected component (island) with a unique ID and compute its size using DFS. Store this information in a map. Then, for each 0 cell, examine its 4 neighbors to identify which distinct islands touch it (using a set to avoid counting the same island multiple times). The potential island size from flipping this 0 is 1 + sum of distinct neighboring island sizes. Track the maximum across all 0 cells, and handle the edge case where the grid is already all 1s.

def largest_island(grid):
    """
    Find the largest island after flipping at most one 0 to 1.
    Uses DFS to label components, then checks each 0 for merge potential.
    """
    if not grid or not grid[0]:
        return 0
    
    n = len(grid)
    island_id = 2  # Start from 2 (0 and 1 are already used)
    island_sizes = {}  # Map island_id -> size
    
    def dfs(r, c, island_id):
        """Label connected 1s with island_id and return size."""
        if r < 0 or r >= n or c < 0 or c >= n:
            return 0
        if grid[r][c] != 1:
            return 0
        
        grid[r][c] = island_id
        size = 1
        
        # Explore all 4 directions
        size += dfs(r + 1, c, island_id)
        size += dfs(r - 1, c, island_id)
        size += dfs(r, c + 1, island_id)
        size += dfs(r, c - 1, island_id)
        
        return size
    
    # Phase 1: Label all islands and compute their 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
                island_id += 1
    
    # Edge case: grid is all 1s
    if not island_sizes:
        return 0
    if len(island_sizes) == 1 and sum(island_sizes.values()) == n * n:
        return n * n
    
    max_size = max(island_sizes.values()) if island_sizes else 0
    
    # Phase 2: Check each 0 for potential merge
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                # Find distinct neighboring islands
                neighbor_islands = set()
                
                for dr, dc in directions:
                    ni, nj = i + dr, j + dc
                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
                        neighbor_islands.add(grid[ni][nj])
                
                # Calculate potential size: 1 (flipped cell) + sum of neighbor island sizes
                potential_size = 1
                for island in neighbor_islands:
                    potential_size += island_sizes[island]
                
                max_size = max(max_size, potential_size)
    
    return max_size

• Connected component labeling with metadata: When you need to merge or analyze groups in a grid, use DFS/BFS to label each component with a unique ID and store its size in a hashmap - this transforms an O(n²) merge query into O(1) lookup, enabling efficient "what-if" analysis without re-traversing.
• Neighbor deduplication with sets: When summing sizes of adjacent islands around a cell, use a set to track unique island IDs before summing - this prevents double-counting when the same island touches a cell from multiple directions (e.g., an L-shaped island touching from north and east).
• Two-phase grid processing pattern: Separate preprocessing (label all components) from query evaluation (test each flip) - this amortizes the cost of component discovery across all potential modifications, turning an O(n⁴) brute force into O(n²).
• All-ones edge case handling: Always check if the grid has no zeros at all before processing - return n² immediately, as the flip logic assumes at least one zero exists and will fail or return incorrect results on a completely filled grid.
• Island merging formula: For each zero cell, the potential island size is 1 (the flipped cell) + sum of unique neighboring island sizes - this captures the insight that flipping connects previously disconnected components through a single bridge point.
• Grid modification without mutation: Instead of actually flipping cells and recalculating, precompute all component metadata once and simulate flips through arithmetic - this read-only approach is faster, parallelizable, and easier to debug than repeatedly modifying state.