LeetCode Solutions Blog

Making A Large Island

Difficulty: Hard

Problem Description

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.

Key Insights

We need to identify all islands (groups of 1s) in the grid.
Each island can be represented by its area (number of connected 1s).
Changing a single 0 to 1 can potentially connect multiple islands.
We should calculate the potential new island size for each 0 by summing the sizes of the adjacent islands.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Solution

To solve the problem, we will use Depth-First Search (DFS) to identify and calculate the sizes of all islands in the grid. We will store the sizes of these islands in a dictionary and use a separate DFS call to explore the grid again to consider each 0. For each 0, we will check its adjacent cells and sum the sizes of the connected islands (without double counting). The maximum size found during this process will be our answer.

Code Solutions

def largestIsland(grid):
    n = len(grid)
    
    # Helper function to perform DFS and calculate island size
    def dfs(x, y, index):
        if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:
            return 0
        grid[x][y] = index  # Mark the cell with the island index
        size = 1  # Current cell
        # Explore all four directions
        size += dfs(x + 1, y, index)
        size += dfs(x - 1, y, index)
        size += dfs(x, y + 1, index)
        size += dfs(x, y - 1, index)
        return size

    island_size = {}
    index = 2  # Start indexing islands from 2
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                size = dfs(i, j, index)
                island_size[index] = size  # Store size of the island
                index += 1  # Increment index for the next island

    max_island_size = max(island_size.values(), default=0)  # Maximum island size found
    # Check for potential island sizes from changing a 0 to 1
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                seen = set()  # To avoid double counting
                current_size = 1  # Include the current 0 turned to 1
                # Check adjacent cells
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
                        island_index = grid[ni][nj]
                        if island_index not in seen:
                            current_size += island_size[island_index]
                            seen.add(island_index)
                max_island_size = max(max_island_size, current_size)

    return max_island_size if max_island_size > 0 else n * n  # Edge case