827. Making a Large Island

827

HardGraph DFS and BFSDFS/flood fill with island-size bookkeepingLabel islands, then merge across one flipped cell

Making a Large Island

Given an n x n binary grid, you may change at most one 0 to a 1. Return the size of the largest island (a 4-directionally connected group of 1s) achievable after the change. If the grid is already all 1s, the whole grid is the island.

Open official problem prompt ↗

In plain English

Compute the maximum island size reachable by turning a single water cell into land, accounting for the merges that one flip can create.

Picture it like this

Two neighboring plots of land separated by a thin canal: build one bridge tile across the canal and the plots become a single estate. You want the bridge that unites the largest combined estate.

Example

Input: grid = [[1,0],[0,1]]
Output: 3
Why: Flipping the 0 at (0,1) connects the two size-1 islands into one island of size 3 (the flipped cell plus both original 1s).

Constraints

n == grid.length == grid[i].length1 <= n <= 500grid[i][j] is 0 or 1

Pattern lesson

See the pattern, then code

Label islands, then merge across one flipped cell

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Brute-force flipping every 0 and re-flooding is too slow. Instead label each island with a unique id and remember its area. A flipped 0 fuses all distinct island ids touching its four neighbors, so its resulting size is 1 plus the sum of those areas — computed in O(1) per candidate after one labeling pass.

New words, made simpleKnow these before the algorithm

Island: A maximal set of 4-directionally connected 1 cells.
Island id: A unique label (2,3,4,...) painted onto every cell of one island.
Flood fill: Traversing and relabeling a whole connected component from one seed cell.
Candidate flip: A 0 cell considered for conversion to 1.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Flip each 0 and recount

Recomputes island sizes for every candidate; far too slow at n=500.

For every 0, set it to 1, run a full island scan, take the max, revert.

Time O((n^2) * n^2) = O(n^4)Space O(n^2)

Best choiceLabel once, then O(1) per flip

Two linear passes; the distinct-id set prevents double-counting the same island touched on two sides.

Assign each island an id and area, then for each 0 sum the distinct neighboring island areas plus one.

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

The rule we keep true

Invariant

After the labeling pass, sizes[label] holds the exact cell count of the island painted with that label, so any flip's merged size is derived without re-traversal.

Why this is correct

Reasoning

Every island is painted with one unique id and its true area is recorded. A flipped 0 can only connect islands adjacent to it; using a set of distinct ids ensures an island bordering the flip on two sides is counted once. Seeding best with the largest existing island covers grids where no flip helps (e.g. all 1s or isolated single flips).

The algorithm in three movesSay these aloud before coding

1Flood-fill each island, assigning ids 2,3,4,... and storing id -> area in a map

sizes = {2:1, 3:1}

2Track the best existing island area (covers the case where no beneficial flip exists)

flip (0,1): neighbors ids {2,3} -> 1+1+1 = 3

3For every 0 cell, collect the set of distinct island ids among its 4 neighbors

best = 3

4Its merged size is 1 + sum of those distinct areas; update the best

5Return the best; if the grid was all 1s there are no 0s and the single island area wins

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1(id2)0

1(id3)3

1 · Readscan grid

2 · AskAssign ids and areas

3 · Update state(0,0)->id2 area1; (1,1)->id3 area1; sizes={2:1,3:1}

4 · Resultbest initialized to 1.

Key takeaway

Two size-1 islands (ids 2 and 3) merge through the flipped cell into size 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-20Iterative flood fill
Paints an entire island with a unique label using an explicit stack (avoids recursion-depth issues on 500x500 grids) and returns its area.
2
Lines 22-27Labeling pass
Every unvisited 1 seeds a new island with the next id; sizes maps id to area. best captures the largest untouched island.
3
Lines 29-42Evaluate each flip
For each 0, a set of neighboring island ids ensures each adjacent island's area is added at most once, giving the merged size 1 + sum(areas).

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Grid is all 1s -> no 0 cells, best = n*n from the single island
Grid is all 0s -> flipping one cell yields size 1
A 0 with two neighbors belonging to the SAME island -> counted once via the set
Single cell grid [[0]] -> 1; [[1]] -> 1

Common beginner mistakes

Double-counting an island that borders the flipped cell on more than one side (forgetting the distinct-id set)
Starting labels at 0 or 1, which collide with the grid's water/land markers
Forgetting the all-1s case where no flip is possible
Using recursive DFS and hitting Python's recursion limit on large islands

Check your understanding

Why must the neighboring island ids around a candidate 0 be deduplicated before summing their areas?

PyPython 3 · solution.py

Optimal

1class Solution:2    def largestIsland(self, grid: list[list[int]]) -> int:3        n = len(grid)4        sizes: dict[int, int] = {}5        idx = 267        def flood(r: int, c: int, label: int) -> int:8            stack = [(r, c)]9            grid[r][c] = label10            area = 011            while stack:12                x, y = stack.pop()13                area += 114                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):15                    nx, ny = x + dx, y + dy16                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:17                        grid[nx][ny] = label18                        stack.append((nx, ny))19            return area2021        for r in range(n):22            for c in range(n):23                if grid[r][c] == 1:24                    sizes[idx] = flood(r, c, idx)25                    idx += 12627        best = max(sizes.values(), default=0)28        for r in range(n):29            for c in range(n):30                if grid[r][c] == 0:31                    seen: set[int] = set()32                    total = 133                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):34                        nx, ny = r + dx, c + dy35                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] > 1:36                            label = grid[nx][ny]37                            if label not in seen:38                                seen.add(label)39                                total += sizes[label]40                    best = max(best, total)41        return best

Time complexityO(n^2)Optimized

Space complexityO(n^2)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonDoorDash

Making a Large Island

Making a Large Island

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS