LeetCode Solutions Blog

Making A Large Island

Number: 854

Difficulty: Hard

Paid? No

Problem Description

Given an n x n binary matrix, you can change at most one 0 to 1. After changing a single 0, return the size of the largest possible island created by connecting adjacent 1s (using 4-directional connections).

Key Insights

First, identify and label every existing island using DFS/BFS.
Maintain a mapping from island id to its size.
For each 0, examine its four neighbors. Sum the size of distinct adjacent islands and add 1 (for the flipped cell) to compute a candidate island size.
Be careful to avoid counting the same island more than once when summing.
If the grid is full of 1s (i.e. no 0 to flip), then the largest island is the whole grid.

Space and Time Complexity

Time Complexity: O(n^2) because each cell is visited a constant number of times. Space Complexity: O(n^2) for the recursion/queue in DFS/BFS in the worst case and for storing island information.

Solution

The solution uses a two-phase algorithm. In the first phase, we use DFS to label each island with a unique id (starting from 2 to avoid confusion with 0 and 1) and record its area in a mapping (dictionary). In the second phase, for each cell that is 0, we look at its 4-directional neighbors to find distinct islands. We then sum the sizes of these islands and add 1 (for converting the current 0 into a 1), tracking the maximum island size possible. This approach efficiently calculates the largest island that can be created after a single modification.

Code Solutions

# Python solution for Making A Large Island
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        island_size = {}  # Map island id to island area
        island_id = 2    # Start island ids from 2
        
        # Helper function: DFS to label the islands
        def dfs(i, j, id):
            if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = id  # Label the cell with the island id
            size = 1
            # Visit neighbors (4-directionally)
            size += dfs(i + 1, j, id)
            size += dfs(i - 1, j, id)
            size += dfs(i, j + 1, id)
            size += dfs(i, j - 1, id)
            return size
            
        # First pass: identify each island and record its size.
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:  # Found an unlabeled island cell
                    size = dfs(i, j, island_id)
                    island_size[island_id] = size
                    island_id += 1

        # If no 0 cell exists, then the entire grid is already one island.
        max_area = max(island_size.values()) if island_size else 0

        # Second pass: Try changing each 0 to 1 and calculate the connected island area.
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    seen_islands = set()
                    current_area = 1  # Count the flip (0 -> 1)
                    for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                        ni, nj = i + di, j + dj
                        if 0 <= ni < n and 0 <= nj < n:
                            id = grid[ni][nj]
                            if id > 1 and id not in seen_islands:
                                seen_islands.add(id)
                                current_area += island_size[id]
                    max_area = max(max_area, current_area)
                    
        return max_area