1. Union Find

Intuition

We need to track islands dynamically as land cells are added one at a time. Union-Find is ideal for this because it efficiently merges sets and counts distinct groups. Each time we add a land cell, we check its four neighbors. If a neighbor is already land, we union the new cell with that neighbor. The island count increases by 1 for each new land cell added, then decreases by 1 for each successful union with an adjacent island.

Algorithm

  1. Initialize a Union-Find structure with all cells marked as water (parent = -1) and island count = 0.
  2. For each position in the positions array:
    • If this cell is already land, record the current count and continue.
    • Mark the cell as land, set its parent to itself, and increment the island count.
    • Check all four neighbors (up, down, left, right). For each neighbor that is land, union it with the new cell (this decrements the count if they were in different sets).
    • Append the current island count to the result.
  3. Return the result array.
class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [0] * size
        self.count = 0
    
    def add_land(self, x):
        if self.parent[x] >= 0:
            return
        self.parent[x] = x
        self.count += 1
    
    def is_land(self, x):
        if self.parent[x] >= 0:
            return True
        else:
            return False
    
    def number_of_islands(self):
        return self.count
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        xset = self.find(x)
        yset = self.find(y)
        
        if xset == yset:
            return
        elif self.rank[xset] < self.rank[yset]:
            self.parent[xset] = yset
        elif self.rank[xset] > self.rank[yset]:
            self.parent[yset] = xset
        else:
            self.parent[yset] = xset
            self.rank[xset] += 1
        
        self.count -= 1


class Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        x = [-1, 1, 0, 0]
        y = [0, 0, -1, 1]
        dsu = UnionFind(m * n)
        answer = []
        
        for position in positions:
            land_position = position[0] * n + position[1]
            dsu.add_land(land_position)
            
            for i in range(4):
                neighbor_x = position[0] + x[i]
                neighbor_y = position[1] + y[i]
                neighbor_position = neighbor_x * n + neighbor_y
                
                # If neighborX and neighborY correspond to a point in the grid and there is a
                # land at that point, then merge it with the current land.
                if neighbor_x >= 0 and neighbor_x < m and neighbor_y >= 0 and neighbor_y < n and dsu.is_land(neighbor_position):
                    dsu.union(land_position, neighbor_position)
            
            answer.append(dsu.number_of_islands())
        
        return answer

Time & Space Complexity

  • Time complexity: O(m⋅n+l)O(m \cdot n + l)
  • Space complexity: O(m⋅n)O(m \cdot n)

Where mm and nn are the number of rows and columns in the given grid, and ll is the size of positions.