Number of Islands II

Table of Contents +

You start with all water. Then land appears one cell at a time. After each new piece of land, how many separate islands exist right now? Recounting the whole grid every time is wasteful. The clean fix grows the answer as the land arrives.

🎯 The Problem

Land appears one cell at a time. After each new cell, you report how many islands exist.

The rules:

The grid starts as all water, which is 0.
Each addition [r, c] turns that cell into land, which is 1.
An island is a group of land cells joined up, down, left, or right.
After every addition, report how many separate islands exist right now.
Return the list of counts, one per addition.

Input:
  m = 3, n = 3
  positions = [[0, 0], [0, 1], [1, 2], [2, 1]]

Output: [1, 1, 2, 3]

Explanation:
  Add (0,0): one island.                      -> 1
  Add (0,1): touches (0,0), still one island. -> 1
  Add (1,2): alone, a second island.          -> 2
  Add (2,1): alone, a third island.           -> 3

So you return a list with one count after each addition.

Here is the grid after all additions. Land cells that touch form one island. The cell at (1,2) and the cell at (2,1) each stand alone.

🐢 Approach 1: Recount The Whole Grid Every Time (Brute Force)

The idea in one line: after each addition, sweep the whole grid and count islands from scratch.

The idea:

Add the new land cell.
Sweep the grid and count islands with flood fill.
Flood fill starts at each unvisited land cell and walks to all connected land cells.

How it works:

For each addition, turn the cell to land.
Run a full island count over the whole grid.
Record that count.

Why it is weak:

Every addition triggers a full grid sweep.
With k additions on an m × n grid, the cost climbs to O(k × m × n).
You keep recounting the same regions again and again.

Here is the recount-after-each-add code:

def num_islands2(m, n, positions):
    grid = [[0] * n for _ in range(m)]
    def count():
        seen = set()
        def dfs(r, c):
            if r < 0 or c < 0 or r == m or c == n or grid[r][c] == 0 or (r, c) in seen: return
            seen.add((r, c)); dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
        total = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] and (r, c) not in seen:
                    total += 1; dfs(r, c)
        return total
    ans = []
    for r, c in positions:
        grid[r][c] = 1; ans.append(count())
    return ans

⚡ Approach 2: Union-Find, One Cell At A Time (Best)

The idea in one line: do not recount. Adjust the running count as each cell arrives.

The idea:

This is a dynamic connectivity problem. Connections are added over time and you answer questions in between.
Union-find is built exactly for this.

How it works:

Keep a running island count.
When a new land cell appears, add one to the count. On its own it is a brand new island.
Look at its four neighbors. For each neighbor that is already land and in a different group, union them.
Each successful union merges two islands into one, so subtract one from the count.
Record the count after each addition.

Watch the duplicate:

The same cell might be added twice in the input.
If a cell is already land, do not add it again and do not change the count.

Why it is fast:

Each step touches only the new cell and its four neighbors.
Each union and find is almost constant after path compression.
So the whole run is about O(k) with that near-constant factor.

Here is the count changing as each cell is added.

Steps to Solve

Start with a count of 0 and every cell marked as water.
For each addition, if the cell is already land, record the same count and skip.
Mark the cell as land and add one to the count for this new island.
Check the four neighbors. For each that is land and in a different group, union them and subtract one from the count.
Record the current count.
Return the list of counts.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version keeps parent links in a list and a set of land cells, updating the count as each cell arrives.

def num_islands_ii(m, n, positions):
    parent = list(range(m * n))       # each cell is its own group
    land = set()                      # cells that are currently land
    count = 0
    result = []

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

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

    for r, c in positions:
        idx = r * n + c
        if idx in land:               # duplicate add, nothing changes
            result.append(count)
            continue
        land.add(idx)
        count += 1                    # this new cell is its own island for now
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                nidx = nr * n + nc
                if nidx in land and find(idx) != find(nidx):
                    parent[find(idx)] = find(nidx)  # merge the two islands
                    count -= 1                      # two became one
        result.append(count)

    return result


m, n = 3, 3
positions = [[0, 0], [0, 1], [1, 2], [2, 1]]
print(num_islands_ii(m, n, positions))

The output of the above code will be:

[1, 1, 2, 3]

Let us read the Python version line by line, because the count adjustment is the clever part.

parent = list(range(m * n)) gives every cell its own group at the start, even the water cells. We only join a cell to others once it becomes land.

land is a set of cell ids that are land right now. count is the live island count. result collects the count after each addition.

find(x) climbs to the group root, with path compression on the way to keep it fast.

For each added cell we compute its flat id idx = r * n + c. If that id is already in land, the cell was added before, so nothing changes. We append the same count and skip. This is the duplicate guard.

If it is new, we add it to land and do count += 1. We assume it is a fresh island. That assumption may be wrong if it touches existing land, which we fix next.

The neighbor loop checks each of the four sides. If a neighbor is land and sits in a different group, we union them and do count -= 1. Two islands just merged into one, so the count drops. The check find(idx) != find(nidx) matters. If the cell already merged with this island through another side, the roots are equal, so we do not subtract twice.

After the neighbors are handled, we append the corrected count. Walk the example and you get 1, then 1, then 2, then 3.

⏱️ Time and Space Complexity

The brute force recounts the whole grid after each of the k additions, so it is O(k × m × n). Union-find touches only the new cell and its four neighbors per step, and each find or union is almost constant after path compression. So it runs in about O(k) with that near-constant factor. Both store parent links sized to the grid, which is O(m × n) space.

Approach	Time Complexity	Space Complexity
Recount with flood fill	O(k × m × n)	O(m × n)
Union-find one cell at a time	O(k × α)	O(m × n)

Tip

The count rule is simple once you see it. Every new land cell adds one island. Every successful merge removes one. Add first, then subtract for each distinct neighbor you join.

🧩 Key Takeaways

✅ Do not recount the grid. Adjust the running count as each cell arrives.
✅ A new land cell adds one island. Each merge with a neighbor removes one.
✅ Use union-find so each merge and lookup is almost constant time.
✅ Check the find roots before merging so you never subtract twice for one island.
✅ Guard against duplicate additions by skipping cells that are already land.

Check Your Knowledge

4 questions Show quiz Hide quiz

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

🚀 What’s Next?

Previous Bus Routes Next Reconstruct Itinerary

Number of Islands II

Follow Us

Follow Us