Hard

Making A Large Island

LAB

Given a binary grid, return the largest island area possible after changing at most one 0 to 1.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      0
    ],
    [
      0,
      1
    ]
  ]
}

Output
3

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Idea: colour each island a certain number. Create a map: colour num -> area of island. At every 0, do 1 + area of unique adjacent islands. Take maximum. O(n^2) time, O(n^2) space for dfs stack. Actually pretty straightforward. Watch out for edge case of no 0's in the grid.

Reveal reference solution +

pythonREFERENCE

def largestIsland(self, grid: List[List[int]]) -> int:
    n = len(grid)
    color = 2
    area_map = {}

    def dfs(x, y, color):
        if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:
            return 0
        grid[x][y] = color
        area = 1
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            area += dfs(x + dx, y + dy, color)
        return area

    # First pass: color each island and store its area
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                area_map[color] = dfs(i, j, color)
                color += 1

    max_area = max(area_map.values(), default=0)
    has_zero = False

    # Second pass: try flipping each 0 to 1
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                has_zero = True
                seen = set()
                for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                    ni, nj = i + dx, j + dy
                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
                        seen.add(grid[ni][nj])
                max_area = max(max_area, 1 + sum(area_map[c] for c in seen))
    return max_area if has_zero else n * n

TimeO(n^2)

SpaceO(n^2)

Open on LeetCode ↗