Make the largest island: A Sample Coding Interview Solution

The coding question

You're given a grid of 0s and 1s. You can change at most one 0 to a 1. Return the size of the largest island you can end up with.

Ask a few questions first

Ask	What we'll assume
What counts as connected?	Up, down, left and right. Not diagonals.
Do I have to flip a 0?	No, at most one. If the grid is all 1s, the answer is the whole grid.
What if the grid is all 0s?	Flip one, so the answer is 1.
How big can the grid be?	Up to 500 by 500, so 250,000 cells.

A couple of examples

Input	Output
[[1, 0], [0, 1]]	3
[[1, 1], [1, 0]]	4
[[1, 1], [1, 1]]	4

Start with brute force

For every 0, flip it to 1, flood fill the whole grid to find the biggest island, then flip it back.

Cost: O((rows × cols) squared). With 250,000 cells that's tens of billions of steps, so it times out.

A better way

When you flip a 0, the new island is that cell plus every island touching it. You don't need to flood fill again to know those sizes. Work out each island's size once and look it up.

So do one pass that gives every island an ID and records its size in a hash map. Then for each 0, look at its four neighbors, collect the distinct island IDs, and add their sizes plus 1. Use a set for the IDs, because the same island often touches a 0 from two sides.

Make a label grid of zeros. Walk every cell, and when you hit a 1 with no label, flood fill from it with a new ID and save the island's size.
Start the best answer at the biggest island, or 0 if there are none.
For each 0, gather the distinct IDs of its neighbors, and score 1 plus their sizes.
Keep the biggest score and return it.

The code

solution.pypython

def largest_island(grid):
    n_rows, n_cols = len(grid), len(grid[0])
    label = [[0] * n_cols for _ in range(n_rows)]
    sizes = {}
    next_id = 1
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for r in range(n_rows):
        for c in range(n_cols):
            if grid[r][c] == 1 and label[r][c] == 0:
                label[r][c] = next_id
                stack = [(r, c)]
                size = 0
                while stack:
                    cr, cc = stack.pop()
                    size += 1
                    for dr, dc in directions:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < n_rows and 0 <= nc < n_cols and grid[nr][nc] == 1 and label[nr][nc] == 0:
                            label[nr][nc] = next_id
                            stack.append((nr, nc))
                sizes[next_id] = size
                next_id += 1

    best = max(sizes.values(), default=0)
    for r in range(n_rows):
        for c in range(n_cols):
            if grid[r][c] == 0:
                touching = set()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n_rows and 0 <= nc < n_cols and label[nr][nc]:
                        touching.add(label[nr][nc])
                best = max(best, 1 + sum(sizes[i] for i in touching))
    return best

	Cost	Why
Time	O(rows × cols)	Each cell is labeled once, then each 0 checks four neighbors
Space	O(rows × cols)	The label grid, the stack and the size map

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

All 1s, like [[1, 1], [1, 1]]: there's no 0 to flip, so the answer is the whole grid, 4.
All 0s: no islands, and any flip gives 1.
A single cell, [[0]] or [[1]]: both give 1.
One island wrapping around a 0, like [[1, 1, 0], [1, 0, 1], [0, 1, 1]]: the middle 0 joins two islands and gives 7. The set stops you counting one island twice.

Common mistakes

Adding up neighbor sizes without a set, so an island touching the 0 from two sides gets counted twice.
Forgetting the all-1s grid, where the loop over 0s never runs and the answer is the existing island.
Using recursive DFS on a 500 by 500 grid. A long snake-shaped island can hit Python's recursion limit. Use your own stack.
Marking a cell as visited when you pop it instead of when you push it, so the same cell lands on the stack many times.

Follow-up questions

What if you can flip up to k zeros?

It gets much harder. For small k you can try combinations, but in general it's a search problem. Talk through why the one-flip trick doesn't extend neatly.

What if the grid changes, with cells turning to land one at a time?

Use union-find. Each new land cell joins its neighbors' sets, and you keep track of the biggest set as you go.

Could you skip the separate label grid?

Yes, write the island IDs into the grid itself, starting from 2 so they don't clash with 0 and 1. Mention that this changes the input.

How the time adds up

Minutes	What you're doing
0–2	Clarify, including the all-1s case. Meta usually wants two problems in about 45 minutes, so you get about 20 for each
2–4	Brute force: flip and flood fill each time
4–8	Explain labeling islands once and the set of neighbors
8–15	Write the code
15–18	Test the examples and the all-1s grid
18–20	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Meta.