Making a Large Island

Table of Contents +

Here is a grid of land and water. You may change exactly one water cell into land. What is the biggest island you can make? This question tests if you can join groups fast, instead of recounting everything again and again.

🎯 The Problem

You flip one water cell to land and ask how big the largest island can get. Here are the rules.

  • You get a square grid. Each cell is 1 for land or 0 for water.
  • An island is a group of land cells joined up, down, left, or right.
  • You may flip at most one 0 into a 1.
  • After that flip, return the size of the largest island.
  • If the grid is already all land, you cannot flip anything, so the answer is the total cell count.

For example, flip the right 0 in the grid below and two separate pieces of land join into one big island.

Input:  grid = [[1, 0],
                [0, 1]]
Output: 3


Explanation: Flip the cell at row 0, col 1 (a 0) to land.
Now the top-left 1, that new cell, and the bottom-right 1 connect into one island of size 3.

Here is the grid drawn as a graph. Each land cell is a node. Each edge joins two land cells that touch.

1 at (0,0)

0 at (0,1)

0 at (1,0)

1 at (1,1)

🐢 Approach 1: Flip and Flood Fill (Brute Force)

The idea in one line: try every water cell as land, count the island that forms around it, and keep the biggest count.

The idea:

  • Try every water cell. Pretend it is land.
  • Count the island that now forms around it.
  • Keep the biggest count you ever see.

How it works:

  • To count an island you use flood fill.
  • Flood fill starts at a cell and walks to every connected land cell.
  • It marks each cell so you never count it twice.
  • You can do this with recursion or a stack.

Why it is weak:

  • For every single 0, you flood the whole region again from scratch.
  • The same land cells get counted over and over.
  • On a grid with n cells this becomes O(n²) time. Too slow when the grid is large.

Here is the flip-each-zero code:

making_large_island_brute_force.py
def largest_island(grid):
    n = len(grid)
    def area(r, c, seen):
        if r < 0 or c < 0 or r == n or c == n or grid[r][c] == 0 or (r, c) in seen:
            return 0
        seen.add((r, c))
        return 1 + area(r+1,c,seen)+area(r-1,c,seen)+area(r,c+1,seen)+area(r,c-1,seen)
    best = 0
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                grid[r][c] = 1
                best = max(best, area(r, c, set()))
                grid[r][c] = 0
    return best or n * n

⚡ Approach 2: Union-Find With Island Sizes (Best)

The idea in one line: count each island once up front, then for each 0 just add up the sizes of the islands touching it.

The idea:

  • Union-find groups cells and answers “which group is this in?” almost instantly.
  • Each group has one root.
  • Keep a size for each root, which is how many cells that island holds.

How it works:

  • First pass: walk the grid. For every land cell, union it with its land neighbors.
  • Now every island is one group with a known size.
  • Second pass: walk the grid again. For every 0, look at its four neighbors.
  • Collect the distinct island roots around it.
  • Add their sizes, plus one for the flipped cell itself.
  • That total is the island you would get by flipping this 0. Track the maximum.

The double-count guard:

  • A 0 might touch the same island on two sides.
  • Use the root, not the raw neighbor.
  • Skip roots you already added. Otherwise you double count.

Why it is fast:

  • Both passes go over the grid a fixed number of times.
  • Each union-find lookup is near constant. So the whole thing is about O(n).

Here is the flow of the optimal solution.

Start

Pass 1: union all touching land into islands with sizes

Pass 2: for each water cell

Find distinct island roots around it

Sum their sizes plus 1

Update the best answer

Return best, or whole grid if no water

Steps to Solve

  1. Give every cell an id based on its row and column.
  2. Walk the grid. For each land cell, union it with its land neighbors so each island becomes one group with a size.
  3. Set the answer to the largest single island size, in case there is no water to flip.
  4. Walk the grid again. For each water cell, gather the distinct island roots in its four neighbors.
  5. Add those island sizes together, plus one for the flipped cell, and update the best answer.
  6. Return the best answer.

This Python version keeps parent and size in lists and uses a set to skip repeated island roots.

large_island.py
def largest_island(grid):
    n = len(grid)
    parent = list(range(n * n))   # each cell starts as its own group
    size = [1] * (n * n)          # each group starts with size 1


    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x


    def unite(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        parent[rb] = ra            # join b's group into a's
        size[ra] += size[rb]       # add their sizes


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


    # Pass 1: union every land cell with its land neighbors
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                        unite(r * n + c, nr * n + nc)


    # biggest island even if we never flip a 0
    best = max((size[find(r * n + c)]
                for r in range(n) for c in range(n) if grid[r][c] == 1),
               default=0)


    # Pass 2: try turning each water cell into land
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                roots = set()
                total = 1               # the flipped cell itself
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                        root = find(nr * n + nc)
                        if root not in roots:
                            roots.add(root)
                            total += size[root]
                best = max(best, total)


    return best




grid = [[1, 0], [0, 1]]
print(largest_island(grid))

The output of the above code will be:

3

Let us walk the Python version line by line, because the two-pass idea is the whole trick.

parent = list(range(n * n)) gives every cell its own group at the start. The cell at row r and column c gets the id r * n + c. That flattens the 2D grid into one list.

size = [1] * (n * n) says every group starts holding one cell.

find(x) climbs from a cell to its group root. The line parent[x] = parent[parent[x]] is path compression. It shortens the climb for next time, so lookups stay almost instant.

unite(a, b) joins two groups. It points one root at the other, then adds the sizes. So the merged island knows its total cell count right away.

The first double loop is pass one. For each land cell it unions with each land neighbor. After this loop every island is a single group with a correct size.

The best = max(...) line handles the case where the grid has no water. Then you cannot flip anything, so the answer is just the largest existing island.

The second double loop is pass two. For each water cell it gathers the roots of the land touching it. The if root not in roots check is the key guard. Without it, a 0 touching the same island twice would add that island’s size twice. We add size[root] for each distinct island, plus the 1 we started total with for the flipped cell itself.

⏱️ Time and Space Complexity

The brute force floods the grid once for every water cell, so it climbs to O(n²). The union-find walks the grid a fixed number of times, and each lookup is nearly constant after path compression. So it lands at about O(n). Both need O(n) extra memory for the parent and size arrays.

Approach Time Complexity Space Complexity
Flip and flood fill (brute force) O(n²) O(n)
Union-find with island sizes (best) O(n) O(n)

Tip

The double-count guard is what interviewers watch for. A water cell can touch the same island on two sides. Use the root and a set, never the raw neighbor.

🧩 Key Takeaways

  • ✅ Count every island once with union-find, then reuse those sizes for each flip.
  • ✅ Each island is one group with a stored size, so adding sizes is instant.
  • ✅ For each water cell, sum the distinct neighbor islands plus one for the flip.
  • ✅ Use the root and a set so you never add the same island twice.
  • ✅ Handle the all-land grid by starting best at the largest existing island.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What can you change in this problem?

    Why: You may flip at most one 0 into a 1, then measure the largest island.

  2. 2

    Why is the brute force flood-fill approach slow?

    Why: Re-flooding for each 0 recounts the same land repeatedly, giving O(n²) time.

  3. 3

    When summing islands around a water cell, why use a set of roots?

    Why: A 0 can border the same island on multiple sides, so distinct roots prevent double counting.

  4. 4

    What is the time complexity of the union-find approach?

    Why: Two passes over the grid with almost constant lookups give roughly O(n) total.

Score: 0 / 4

🚀 What’s Next?

Previous Shortest Path in Binary Matrix Next Evaluate Division