LeetCode Solutions Blog

Number of Islands II

Number: 305

Difficulty: Hard

Paid? Yes

Problem Description

Given an initially water-filled m x n grid, you perform a sequence of add-land operations at specified positions. After each operation, return the number of islands present. An island is defined as a group of adjacent lands connected horizontally or vertically.

Key Insights

Use Union Find (Disjoint Set Union) to efficiently manage connected components (islands).
Map 2D grid coordinates to a 1D index.
When adding a new land, check its 4 neighbors (up, down, left, right) and perform unions if they are also lands.
Avoid duplicate processing if the same cell is added multiple times.
Maintain a counter for islands that is updated during each union operation.

Space and Time Complexity

Time Complexity: O(K * α(mn)) where K is the number of operations and α is the inverse Ackermann function (almost constant time per union/find). Space Complexity: O(mn) for storing the union-find structure.

Solution

The solution relies on the Union Find data structure to dynamically merge islands. When a new land cell is added:

If the cell is already land, record the current island count.
Otherwise, mark the cell as land and increment the island count.
Check the four neighboring cells; if any neighbor is land, attempt to union the current cell with that neighbor.
If a union actually happens (i.e., the two cells were in separate islands), decrement the island counter.
Output the island count after each add-land operation. The key trick is converting 2D indices to a 1D representation (r * n + c) and using path compression along with union by rank in the Union Find implementation for optimal performance.

Code Solutions

# Python implementation using Union Find with path compression and union by rank.
class UnionFind:
    def __init__(self, size):
        # parent: stores parent of each node. -1 indicates water.
        self.parent = [-1] * size
        self.rank = [0] * size
        self.count = 0  # number of islands

    def find(self, x):
        # Find with path compression.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Union the sets; if union is successful, reduce island count.
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        # union by rank.
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        self.count -= 1
        return True

class Solution:
    def numIslands2(self, m, n, positions):
        uf = UnionFind(m * n)
        result = []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        for r, c in positions:
            idx = r * n + c
            # If the position is already land, skip.
            if uf.parent[idx] != -1:
                result.append(uf.count)
                continue
                
            # Mark this cell as land forming a new island.
            uf.parent[idx] = idx
            uf.count += 1
            
            # Union with all 4 neighbors if they are already land.
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                nidx = nr * n + nc
                if 0 <= nr < m and 0 <= nc < n and uf.parent[nidx] != -1:
                    uf.union(idx, nidx)
            result.append(uf.count)
        return result

# Example run:
# s = Solution()
# print(s.numIslands2(3, 3, [[0,0],[0,1],[1,2],[2,1]]))