LeetCode 305: Number of Islands II

Problem Restatement

We are given an empty m x n grid filled with water.

Each operation turns one cell into land.

After every operation, return the current number of islands.

An island is a group of connected land cells connected horizontally or vertically.

The official problem defines:

The grid starts entirely with water. For each position in positions, we add land at that location and report the island count after the addition. (github.com)

Input and Output

Function shape:

def numIslands2(
    m: int,
    n: int,
    positions: list[list[int]],
) -> list[int]:
    ...

Examples

Example:

m = 3
n = 3

positions = [
    [0, 0],
    [0, 1],
    [1, 2],
    [2, 1],
]

Initially:

0 0 0
0 0 0
0 0 0

Add (0, 0):

1 0 0
0 0 0
0 0 0

There is one island.

Output so far:

[1]

Add (0, 1):

1 1 0
0 0 0
0 0 0

The new land touches the existing island, so the island count stays 1.

Output:

[1, 1]

Add (1, 2):

1 1 0
0 0 1
0 0 0

This creates a second separate island.

Output:

[1, 1, 2]

Add (2, 1):

1 1 0
0 0 1
0 1 0

Still disconnected.

Final output:

[1, 1, 2, 3]

First Thought: DFS After Every Operation

One idea is:

1. Add the new land.
2. Scan the entire grid.
3. Run DFS or BFS to count islands.

This works.

But after every operation, we may scan the whole grid again.

If there are many operations, this becomes very slow.

Suppose:

The complexity becomes roughly:

O(k * m * n)

We need something incremental.

Key Insight

When adding one land cell, only nearby cells matter.

The new land can only connect to its four neighbors:

This is a dynamic connectivity problem.

Union-Find, also called Disjoint Set Union (DSU), is designed for this.

Each island becomes one connected component.

When two neighboring lands touch, we merge their components.

Union-Find Structure

We maintain:

Each cell maps to one integer id:

For example, in a 3 x 3 grid:

Union-Find Operations

We need two core operations.

Find

find(x) returns the root of the connected component containing x.

We also use path compression.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])

    return parent[x]

Path compression makes future operations faster.

Union

union(a, b) merges two components.

If the roots are already equal, the cells already belong to the same island.

Otherwise:

1. Merge the two trees.
2. Decrease island count by one.

if root_a != root_b:
    parent[root_b] = root_a
    count -= 1

Algorithm

Initially:

1. All cells are water.
2. Island count is 0.

For each operation (r, c):

1. If the cell is already land, append the current count.
2. Otherwise:
   • Convert the cell to land.
   • Increase island count by one.
3. Check all four neighbors.
4. If a neighbor is land:
   • Union the two cells.
5. Append the island count.

Correctness

Initially, the grid contains no land, so the island count is correctly 0.

When a new land cell is added, it initially forms a new island by itself. Therefore, increasing the count by one is correct.

The only way this new land can affect existing islands is through its four neighboring cells. If a neighboring cell is water, no connection exists. If a neighboring cell is land, then the two cells belong to the same island and their connected components should be merged.

Union-Find maintains exactly one connected component for each island. When two neighboring land cells belong to different components, merging them correctly reduces the island count by one. If they already belong to the same component, no merge occurs and the count stays unchanged.

Since every possible connection caused by the new land is processed, the Union-Find structure always represents the exact island partition of the grid.

Therefore, after every operation, the stored island count is correct.

Complexity

α(n) grows extremely slowly and is effectively constant in practice.

Implementation

class UnionFind:

    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.count = 0

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return False

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

        self.count -= 1

        return True

class Solution:

    def numIslands2(
        self,
        m: int,
        n: int,
        positions: list[list[int]],
    ) -> list[int]:

        uf = UnionFind(m * n)

        land = set()

        ans = []

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

        for r, c in positions:

            if (r, c) in land:
                ans.append(uf.count)
                continue

            land.add((r, c))

            uf.count += 1

            node_id = r * n + c

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if not (0 <= nr < m and 0 <= nc < n):
                    continue

                if (nr, nc) not in land:
                    continue

                neighbor_id = nr * n + nc

                uf.union(node_id, neighbor_id)

            ans.append(uf.count)

        return ans

Code Explanation

The Union-Find constructor initializes:

self.parent = list(range(size))

Each node starts as its own parent.

Initially, every node forms its own component.

rank helps keep trees shallow.

self.rank = [0] * size

The find operation follows parent pointers until reaching the root.

if self.parent[x] != x:
    self.parent[x] = self.find(self.parent[x])

This line performs path compression.

After compression, future searches become faster.

The union method first finds both roots.

root_a = self.find(a)
root_b = self.find(b)

If the roots match, both nodes already belong to the same island.

if root_a == root_b:
    return False

Otherwise, merge the smaller-rank tree under the larger-rank tree.

if self.rank[root_a] < self.rank[root_b]:
    root_a, root_b = root_b, root_a

Then connect:

self.parent[root_b] = root_a

Since two islands became one, reduce the count.

self.count -= 1

Now look at the main solution.

We store land cells in:

land = set()

Water cells are simply absent from the set.

For each new position:

if (r, c) in land:

Duplicate additions do nothing.

Otherwise:

land.add((r, c))
uf.count += 1

The new land starts as a new island.

Convert coordinates to node ids:

node_id = r * n + c

Then inspect all four neighbors.

for dr, dc in directions:

If a neighbor exists and is land:

uf.union(node_id, neighbor_id)

The union operation automatically merges islands if needed.

Finally append the island count.

Testing

def run_tests():
    s = Solution()

    assert s.numIslands2(
        3,
        3,
        [[0, 0], [0, 1], [1, 2], [2, 1]],
    ) == [1, 1, 2, 3]

    assert s.numIslands2(
        1,
        1,
        [[0, 0]],
    ) == [1]

    assert s.numIslands2(
        2,
        2,
        [[0, 0], [1, 1]],
    ) == [1, 2]

    assert s.numIslands2(
        2,
        2,
        [[0, 0], [0, 1], [1, 1]],
    ) == [1, 1, 1]

    assert s.numIslands2(
        3,
        3,
        [[0, 0], [0, 0]],
    ) == [1, 1]

    assert s.numIslands2(
        3,
        3,
        [[0, 0], [1, 0], [2, 0]],
    ) == [1, 1, 1]

    print("all tests passed")

run_tests()

Test meaning: