LeetCode 305 - Number of Islands II

LeetCode Problem 305

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Union-Find

Solution

Problem Understanding

The problem gives us an initially empty m x n grid where every cell starts as water. We are then given a sequence of operations in positions, where each operation turns a specific cell from water into land.

After every operation, we must determine how many islands currently exist in the grid.

An island is formed by horizontally or vertically connected land cells. Diagonal connections do not count. Every newly added land cell can either:

• Create a brand new island
• Attach itself to an existing island
• Merge multiple existing islands into one larger island

The output is an array where answer[i] represents the number of islands after processing the i-th operation.

The constraints are important:

• positions.length <= 10^4
• m * n <= 10^4

A naive approach that recomputes all islands after every operation would be too slow because we may need to process up to 10^4 operations, each potentially scanning the whole grid.

This problem is fundamentally dynamic connectivity. Land cells are added incrementally, and we need an efficient way to determine whether neighboring cells belong to the same connected component.

Several edge cases are especially important:

• Adding land to a position that is already land
• A new cell connecting multiple islands at once
• Very small grids such as 1 x 1
• Long chains of connected additions
• Sparse additions where islands never merge

These cases can easily produce incorrect island counts if connectivity is not handled carefully.

Approaches

Brute Force Approach

The most direct solution is to maintain the entire grid and, after every land addition, recompute the number of islands from scratch using DFS or BFS.

The process would work like this:

1. Add the new land cell.
2. Traverse the entire grid.
3. Whenever an unvisited land cell is found, perform DFS/BFS to mark the whole island.
4. Count how many separate traversals are needed.

This approach is correct because DFS/BFS accurately identifies connected land components.

However, it is inefficient. Suppose we have k operations. For every operation, we may scan all m * n cells and potentially traverse many of them again.

The total complexity becomes:

• O(k * m * n)

With the constraints allowing up to 10^4 operations and 10^4 cells, this becomes too expensive.

Optimal Approach, Union-Find

The key insight is that we do not need to recompute all islands after every operation.

Each operation only changes a single cell. The only connectivity changes occur between that new cell and its four neighbors.

This makes the Union-Find data structure, also called Disjoint Set Union (DSU), a perfect fit.

Union-Find efficiently supports:

• Finding which connected component a cell belongs to
• Merging two connected components
• Detecting whether two cells are already connected

We treat every land cell as a node in a graph. When a new land cell is added:

• It initially forms a new island
• We check its four neighbors
• If neighboring land cells belong to different islands, we union them
• Every successful union reduces the island count by one

With path compression and union by rank/size, Union-Find operations are nearly constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k * m * n)	O(m * n)	Recompute islands after every operation using DFS/BFS
Optimal	O(k * α(m * n))	O(m * n)	Union-Find dynamically maintains connected components

Here, α is the inverse Ackermann function, which grows so slowly that it is effectively constant in practice.

Algorithm Walkthrough

1. Initialize a Union-Find structure.

We create arrays for:

• parent, storing each node's representative
• rank or size, used for balancing unions

Initially, all cells are water, so no valid parent exists yet. 2. Convert 2D coordinates into a 1D index.

Since Union-Find works best with integer node IDs, we map:

index = row * n + col

This guarantees every cell has a unique identifier. 3. Maintain a set of active land cells.

We need to distinguish water from land efficiently.

A hash set allows constant-time checks for whether a cell has already been activated. 4. Process each land addition.

For every (row, col) in positions:

• If the cell is already land:

• The island count does not change

• Append the current count to the result

• Otherwise:

• Add the cell to the land set

• Increment the island count by one because a new isolated island is created initially

5. Check the four neighboring cells.

The neighbors are:

• Up
• Down
• Left
• Right

For each valid neighboring land cell:

• Find the roots of the current cell and neighbor

• If the roots are different:

• Union them

• Decrease island count by one because two islands merged

6. Append the current island count.

After all unions are processed, the current count reflects the correct number of islands. 7. Continue until all operations are processed.

Why it works

The critical invariant is that every connected island corresponds to exactly one connected component in the Union-Find structure.

Whenever a new land cell is added:

• It starts as its own component
• Any adjacent land cells represent islands that should be connected
• Every successful union merges two distinct islands into one

Therefore, the island counter always matches the number of connected components among land cells.

Python Solution

from typing import List

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = {}
        rank = {}

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> bool:
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return False

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

            return True

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

        land = set()
        island_count = 0
        result = []

        for row, col in positions:
            if (row, col) in land:
                result.append(island_count)
                continue

            land.add((row, col))

            current = row * n + col
            parent[current] = current
            rank[current] = 0

            island_count += 1

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < m
                    and 0 <= new_col < n
                    and (new_row, new_col) in land
                ):
                    neighbor = new_row * n + new_col

                    if union(current, neighbor):
                        island_count -= 1

            result.append(island_count)

        return result

The implementation uses dictionaries for parent and rank rather than fixed-size arrays. This avoids initializing all m * n cells up front because only land cells participate in Union-Find operations.

The find function performs path compression. Every time we traverse parent pointers, we flatten the structure so future lookups become faster.

The union function merges two components using union by rank. This prevents the trees from becoming tall and keeps operations efficient.

The land set tracks which cells are currently land. This is essential because neighboring coordinates may still be water.

For every operation:

• Duplicate additions are ignored
• The new land cell starts as a separate island
• Neighbor checks attempt to merge adjacent islands
• Every successful merge decreases the island count

The result array records the number of islands after each operation.

Go Solution

package main

func numIslands2(m int, n int, positions [][]int) []int {
	parent := make(map[int]int)
	rank := make(map[int]int)

	var find func(int) int

	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x int, y int) bool {
		rootX := find(x)
		rootY := find(y)

		if rootX == rootY {
			return false
		}

		if rank[rootX] < rank[rootY] {
			parent[rootX] = rootY
		} else if rank[rootX] > rank[rootY] {
			parent[rootY] = rootX
		} else {
			parent[rootY] = rootX
			rank[rootX]++
		}

		return true
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	land := make(map[int]bool)

	islandCount := 0
	result := []int{}

	for _, pos := range positions {
		row := pos[0]
		col := pos[1]

		current := row*n + col

		if land[current] {
			result = append(result, islandCount)
			continue
		}

		land[current] = true

		parent[current] = current
		rank[current] = 0

		islandCount++

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow < 0 || newRow >= m || newCol < 0 || newCol >= n {
				continue
			}

			neighbor := newRow*n + newCol

			if !land[neighbor] {
				continue
			}

			if union(current, neighbor) {
				islandCount--
			}
		}

		result = append(result, islandCount)
	}

	return result
}

The Go implementation follows the same logic as the Python version but uses maps instead of dictionaries and closures for the find and union functions.

Go does not have built-in tuples, so positions are handled using integer encoding directly. The land map stores active land cells using their 1D index.

Integer overflow is not a concern because the maximum index is at most 10^4.

Worked Examples

Example 1

Input:

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

Initial state:

All water
Island count = 0

Step	Operation	Action	Island Count
1	(0,0)	New isolated land	1
2	(0,1)	Adjacent to (0,0), union occurs	1
3	(1,2)	Separate island	2
4	(2,1)	Separate island	3

Detailed Union-Find State

Step 1: Add (0,0)

Index:

0 * 3 + 0 = 0

State:

parent = {0: 0}

Island count:

1

Step 2: Add (0,1)

Index:

0 * 3 + 1 = 1

Neighbor (0,0) already exists.

Union:

union(1, 0)

State after union:

parent = {
    0: 1,
    1: 1
}

Island count decreases from 2 to 1.

Step 3: Add (1,2)

Index:

1 * 3 + 2 = 5

No neighboring land exists.

Island count becomes:

2

Step 4: Add (2,1)

Index:

2 * 3 + 1 = 7

No neighboring land exists.

Island count becomes:

3

Final output:

[1,1,2,3]

Example 2

Input:

m = 1
n = 1
positions = [[0,0]]

Step	Operation	Island Count
1	(0,0)	1

Final output:

[1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k * α(m * n))	Each operation performs a constant number of Union-Find operations
Space	O(m * n)	Parent/rank structures may store every cell

The dominant work comes from Union-Find operations. With path compression and union by rank, each find and union operation runs in amortized nearly constant time.

Since each position checks at most four neighbors, the total complexity is effectively linear in the number of operations.

Test Cases

from typing import List

class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        parent = {}
        rank = {}

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

        def union(x, y):
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return False

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

            return True

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

        land = set()
        island_count = 0
        result = []

        for row, col in positions:
            if (row, col) in land:
                result.append(island_count)
                continue

            land.add((row, col))

            current = row * n + col
            parent[current] = current
            rank[current] = 0

            island_count += 1

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < m
                    and 0 <= nc < n
                    and (nr, nc) in land
                ):
                    neighbor = nr * n + nc

                    if union(current, neighbor):
                        island_count -= 1

            result.append(island_count)

        return result

sol = Solution()

assert sol.numIslands2(
    3, 3,
    [[0,0],[0,1],[1,2],[2,1]]
) == [1,1,2,3]  # Provided example

assert sol.numIslands2(
    1, 1,
    [[0,0]]
) == [1]  # Single cell grid

assert sol.numIslands2(
    2, 2,
    [[0,0],[1,1]]
) == [1,2]  # Two disconnected islands

assert sol.numIslands2(
    2, 2,
    [[0,0],[0,1],[1,1]]
) == [1,1,1]  # Continuous merging

assert sol.numIslands2(
    3, 3,
    [[0,0],[0,1],[1,1],[1,0]]
) == [1,1,1,1]  # Forms one connected block

assert sol.numIslands2(
    3, 3,
    [[0,0],[0,0],[1,1]]
) == [1,1,2]  # Duplicate land addition

assert sol.numIslands2(
    3, 3,
    [[0,0],[0,2],[2,2],[2,0]]
) == [1,2,3,4]  # No adjacent connections

assert sol.numIslands2(
    3, 3,
    [[0,0],[0,1],[1,0],[1,1]]
) == [1,1,1,1]  # Multiple unions into same island

Test	Why
[[0,0],[0,1],[1,2],[2,1]]	Validates standard behavior
1x1 grid	Smallest possible input
Two separate cells	Ensures disconnected islands counted separately
Sequential merges	Verifies unions reduce island count correctly
Full connected block	Tests repeated neighbor unions
Duplicate additions	Ensures duplicate land does not change state
Completely separated corners	Confirms no accidental diagonal merging
Dense neighboring additions	Tests handling of already-connected neighbors

Edge Cases

One important edge case is duplicate land additions. A naive implementation might accidentally increase the island count again when the same position appears multiple times. The solution avoids this by maintaining a land set. If a cell already exists in the set, the current island count is appended directly without performing any unions.

Another critical edge case occurs when a newly added land cell connects multiple islands simultaneously. For example, a center cell might touch land on several sides. Without careful Union-Find checks, the implementation could incorrectly decrement the island count multiple times for the same connected component. The union function prevents this by returning False when two cells are already in the same set.

Small grids such as 1 x 1 are also important. Some implementations accidentally assume neighboring cells always exist or mishandle bounds checking. This solution explicitly verifies neighbor coordinates remain within valid grid boundaries before attempting any connectivity operations.

A final subtle edge case involves diagonal cells. The problem specifies that only horizontal and vertical adjacency counts. Two diagonal land cells must remain separate islands. Since the algorithm checks only four directions, diagonal cells are never merged incorrectly.