Making A Large Island

Making A Large Island is a grid problem that rewards a two-phase mindset. Instead of re-exploring islands every time you consider a move, you label them once, then read the labels to evaluate every move in constant time.

1 1 0
0 0 1
1 0 1

The slow way first

The obvious idea: for every 0 in the grid, pretend you flip it, run a fresh flood-fill from that cell, and measure the island it would create. That works, but each flip costs an O(n²) traversal, and there are up to n² zeros — so O(n⁴) overall. Far too slow.

The wasteful part is re-walking the same islands over and over. The question to ask: what do I wish I already knew before testing a flip? I wish I already knew the size of every island and could name each one, so that testing a flip is just a quick lookup.

The idea: label once, then probe

Do it in two passes:

1. Flood-fill every island with a unique id (start ids at 2, since 0 and 1 are taken). As you fill, record sizes[id] = size. Now each land cell literally stores which island it belongs to.
2. For each water cell, look at its up/down/left/right neighbors, collect the unique island ids around it, and add up sizes[id] for each — plus 1 for the flipped cell itself. The biggest such total is the answer.

The unique part matters: a single 0 can touch the same island on two sides. If you do not dedupe by id, you would double-count that island. Using a set of ids fixes it for free.

Walk through it

Step through the animation. First the three islands light up in their own colors as flood-fill labels them — A and B have size 2, C has size 1. Then the flip pointer visits each 0: flipping (1,0) joins A and C for 4; flipping the center (1,1) joins A and B for 5; flipping (0,2) only reaches B for 3. The best, 5, wins.

Pseudocode

nid = 2                                   # first island id (0=water, 1=unlabeled land)
for every land cell not yet labeled:
    size = flood-fill it, painting every reached cell with nid
    sizes[nid] = size; nid += 1
best = largest island size so far         # answer if no flip helps
for every water cell (r, c):
    ids = set of neighbor labels > 1 around (r, c)   # unique island ids
    best = max(best, 1 + sum(sizes[i] for i in ids))
return best

The Python solution

def largest_island(grid):
    n = len(grid)
    sizes, nid = {}, 2          # ids start at 2 (0=water, 1=unlabeled)
    def fill(r, c, i):          # flood-fill, return island size
        if not (0 <= r < n and 0 <= c < n) or grid[r][c] != 1:
            return 0
        grid[r][c] = i
        return 1 + sum(fill(r+dr, c+dc, i) for dr, dc in DIRS)
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                sizes[nid] = fill(r, c, nid); nid += 1
    best = max(sizes.values(), default=0)
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                ids = {grid[r+dr][c+dc] for dr, dc in DIRS
                       if 0 <= r+dr < n and 0 <= c+dc < n and grid[r+dr][c+dc] > 1}
                best = max(best, 1 + sum(sizes[i] for i in ids))
    return best

• sizes maps an island id → its size; nid is the next id to hand out, starting at 2.
• fill is a DFS that overwrites each reached 1 with the island id i and returns the count of cells it painted. Overwriting in place doubles as the visited-marker.
• The first double loop labels every island once and stores its size.
• best starts as the largest existing island, so a grid with no useful flip still returns the right answer.
• For each 0, the set comprehension gathers the unique neighbor ids greater than 1 (real islands). Summing sizes[i] over that set, plus 1 for the flip, gives the merged size — and we keep the max.

Complexity

We touch each cell a constant number of times across both passes, so the whole thing is O(n²) — linear in the number of cells. The extra space is the sizes map plus recursion, both O(n²) in the worst case.

When this pattern shows up

Practice