LeetCode 827: Making A Large Island

Problem Restatement

We are given an n x n binary grid.

Each cell is either:

An island is a group of land cells connected in four directions:

up, down, left, right

We may change at most one 0 into 1.

Return the largest possible island size after doing this operation.

If the grid is already all land, we return the size of the whole grid.

Input and Output

Function shape:

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        ...

Examples

Example 1:

grid = [
    [1, 0],
    [0, 1],
]

There are two separate islands, each with size 1.

If we flip the top-right 0, the grid becomes:

[
    [1, 1],
    [0, 1],
]

Now the island has size 3.

So the answer is:

3

Example 2:

grid = [
    [1, 1],
    [1, 0],
]

There is already one island of size 3.

If we flip the only 0, the full grid becomes land.

So the answer is:

4

Example 3:

grid = [
    [1, 1],
    [1, 1],
]

There is no 0 to flip.

The largest island is already the whole grid.

So the answer is:

4

First Thought: Brute Force

A direct approach is:

1. Try every 0 cell.
2. Temporarily change it to 1.
3. Run DFS or BFS to find the largest island.
4. Restore the cell back to 0.

This works, but it repeats a lot of work.

Code sketch:

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        answer = 0

        def dfs(r: int, c: int, seen: set[tuple[int, int]]) -> int:
            if r < 0 or r >= n or c < 0 or c >= n:
                return 0
            if grid[r][c] == 0 or (r, c) in seen:
                return 0

            seen.add((r, c))
            return (
                1
                + dfs(r + 1, c, seen)
                + dfs(r - 1, c, seen)
                + dfs(r, c + 1, seen)
                + dfs(r, c - 1, seen)
            )

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    grid[r][c] = 1

                    seen = set()
                    best = 0

                    for i in range(n):
                        for j in range(n):
                            if grid[i][j] == 1 and (i, j) not in seen:
                                best = max(best, dfs(i, j, seen))

                    answer = max(answer, best)
                    grid[r][c] = 0

        return answer if answer > 0 else n * n

Problem With Brute Force

There can be up to:

n * n

cells.

For every 0, the brute force approach may scan the whole grid again.

Since n can be as large as 500, the grid may contain:

500 * 500 = 250000

cells.

Repeating a full DFS for many zero cells is too slow.

We need to compute island sizes once, then reuse them.

Key Insight

Instead of recalculating islands after every possible flip, label every existing island first.

For each island, give it a unique id and record its size.

For example:

grid = [
    [1, 1, 0],
    [1, 0, 0],
    [0, 1, 1],
]

We can relabel it as:

grid = [
    [2, 2, 0],
    [2, 0, 0],
    [0, 3, 3],
]

Now:

size[2] = 3
size[3] = 2

When checking a 0, we only look at its four neighbors.

If those neighbors belong to islands 2 and 3, flipping this 0 would create:

1 + size[2] + size[3]

The 1 is the flipped cell itself.

We must be careful not to count the same island twice.

Algorithm

Use two phases.

Phase 1: Label islands.

1. Start island ids from 2.
2. Scan every cell.
3. When we find a 1, run DFS from it.
4. Change every cell in that island from 1 to the current island id.
5. Store the island size in a dictionary.

We start ids from 2 because:

Phase 2: Try flipping each 0.

For each 0 cell:

1. Look at its four neighbors.
2. Collect distinct island ids.
3. Sum their sizes.
4. Add 1 for the flipped cell.
5. Update the answer.

If there is no 0, the answer is n * n.

Walkthrough

Use:

grid = [
    [1, 0],
    [0, 1],
]

First, label islands.

The top-left island gets id 2:

grid = [
    [2, 0],
    [0, 1],
]

Its size is:

size[2] = 1

The bottom-right island gets id 3:

grid = [
    [2, 0],
    [0, 3],
]

Its size is:

size[3] = 1

Now try each 0.

At cell (0, 1), its neighboring islands are 2 and 3.

So flipping it gives:

1 + size[2] + size[3] = 3

At cell (1, 0), the same result is possible.

So the answer is:

3

Correctness

After phase 1, every original island has exactly one unique id.

The DFS visits all land cells connected to the starting cell and assigns the same id to all of them. It does not visit water cells, and it does not cross island boundaries. Therefore, each recorded size is exactly the number of cells in that island.

Now consider any 0 cell. If we flip it to 1, it can only connect islands adjacent to it in the four directions. It cannot connect to islands farther away without a direct path through land.

So the new island formed by flipping this cell has size equal to:

1 + sum(size[id] for each distinct neighboring island id)

The distinct-id set prevents counting the same island multiple times when the flipped cell touches the same island from more than one side.

The algorithm checks every possible 0 cell, computes the exact island size produced by flipping it, and takes the maximum. If there is no 0, no flip is possible, and the whole grid is already one island of size n * n.

Therefore, the algorithm returns the largest possible island size.

Complexity

The grid is modified in place, so we do not need a separate visited matrix.

Implementation

class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        sizes = {}
        island_id = 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int, island_id: int) -> int:
            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
            area = 1

            for dr, dc in directions:
                area += dfs(r + dr, c + dc, island_id)

            return area

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    sizes[island_id] = dfs(r, c, island_id)
                    island_id += 1

        answer = max(sizes.values(), default=0)

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    seen = set()

                    for dr, dc in directions:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            neighbor_id = grid[nr][nc]
                            if neighbor_id > 1:
                                seen.add(neighbor_id)

                    area = 1
                    for neighbor_id in seen:
                        area += sizes[neighbor_id]

                    answer = max(answer, area)

        return answer

Code Explanation

We store each island’s size here:

sizes = {}

The first island id is 2:

island_id = 2

This avoids conflict with 0 and 1.

The DFS labels one full island:

def dfs(r: int, c: int, island_id: int) -> int:

If the cell is outside the grid or not unvisited land, it contributes 0:

if r < 0 or r >= n or c < 0 or c >= n:
    return 0
if grid[r][c] != 1:
    return 0

Otherwise, we mark it with the island id:

grid[r][c] = island_id

Then we count it and continue in four directions.

After all islands are labeled, we start with the largest existing island:

answer = max(sizes.values(), default=0)

This handles cases where the best move is effectively no move, such as an all-land grid.

Then for each water cell, we collect neighboring island ids:

seen = set()

The set matters because one island can touch the same 0 from multiple sides.

For example:

[
    [1, 1],
    [1, 0],
]

The 0 touches the same island from above and left. We should add that island size only once.

Finally, we compute:

area = 1
for neighbor_id in seen:
    area += sizes[neighbor_id]

and update the answer.

Testing

def run_tests():
    s = Solution()

    assert s.largestIsland([
        [1, 0],
        [0, 1],
    ]) == 3

    assert s.largestIsland([
        [1, 1],
        [1, 0],
    ]) == 4

    assert s.largestIsland([
        [1, 1],
        [1, 1],
    ]) == 4

    assert s.largestIsland([
        [0, 0],
        [0, 0],
    ]) == 1

    assert s.largestIsland([
        [1, 1, 0],
        [1, 0, 0],
        [0, 1, 1],
    ]) == 6

    print("all tests passed")

run_tests()

Test meaning: