Solution Explanation: Number of Islands II

This problem asks to find the number of islands after each land operation. An efficient approach uses the Union-Find data structure.

Understanding the Problem

We're given an initially empty grid (all water). We add land cells one by one, specified by positions. After each addition, we need to count the number of islands. An island is a group of connected land cells (horizontally or vertically).

Union-Find Algorithm

Union-Find is ideal for tracking connected components. It maintains a set of disjoint sets (initially each land cell is its own set). The core operations are:

• find(x): Finds the representative element (root) of the set containing element x. Uses path compression for optimization.
• union(x, y): Merges the sets containing elements x and y.

Algorithm Steps

1. Initialization:

   • Create a grid to represent the map (initially all 0s).
   • Create a UnionFind data structure with m * n elements (representing all possible cells).
   • Initialize cnt (island count) to 0.
   • Initialize the ans list to store the island counts after each operation.

2. Iterate through Positions:

   • For each [r, c] in positions:
     • If grid[r][c] is already 1 (land), add the current cnt to ans and continue.
     • Otherwise, set grid[r][c] to 1, increment cnt, and:
       • Check the four adjacent cells:
         • If an adjacent cell is land (grid[x][y] == 1) and it's not already in the same set as (r, c) (check using union()), then merge the sets using union(r*n + c, x*n + y) and decrement cnt (because two islands merged).
       • Add the updated cnt to ans.

Time Complexity Analysis

• The outer loop iterates k times (number of positions).
• Inside the loop, the find and union operations of the Union-Find data structure take almost constant time on average due to path compression and union by rank (or size). The amortized time complexity is close to O(α(n)), where α is the inverse Ackermann function, which is practically a constant for all practical input sizes.
• Checking adjacent cells takes constant time.
• Therefore, the overall time complexity is O(k), where k is the number of positions. This is better than the suggested O(k log(mn)) which might be achieved with different Union Find implementations.

Space Complexity Analysis

• grid: O(mn)
• UnionFind: O(mn) for parent and size arrays.
• ans: O(k)
• Therefore, the overall space complexity is O(mn + k).

Code Implementation (Python)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
 
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
 
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.size[root_i] < self.size[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            self.size[root_i] += self.size[root_j]
            return True
        return False
 
def numIslands2(m, n, positions):
    grid = [[0] * n for _ in range(m)]
    uf = UnionFind(m * n)
    ans = []
    count = 0
    for r, c in positions:
        if grid[r][c] == 1:
            ans.append(count)
            continue
        grid[r][c] = 1
        count += 1
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                if uf.union(r * n + c, nr * n + nc):
                    count -= 1
        ans.append(count)
    return ans
 

Implementations in other languages (Java, C++, Go, TypeScript) would follow a similar structure, adapting the Union-Find implementation and array handling to the specifics of each language. The core algorithmic approach remains the same.