Number of Islands II — Union-Find Online Queries

Problem

Given an empty m x n grid and a list of positions to add land, return the island count after each addition.

Approach — Union-Find (DSU)

Maintain a DSU over all cells. For each new land cell, union with adjacent land cells, decrement count when union merges two components.

Time: O(k * α(mn)) | Space: O(mn)

Solutions

Python

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(a,b):
            a,b=find(a),find(b)
            if a==b: return 0
            if rank.get(a,0)<rank.get(b,0): a,b=b,a
            parent[b]=a
            if rank.get(a,0)==rank.get(b,0): rank[a]=rank.get(a,0)+1
            return 1
        res=[]; count=0
        for r,c in positions:
            if (r,c) in parent:
                res.append(count); continue
            parent[(r,c)]=(r,c); count+=1
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc=r+dr,c+dc
                if (nr,nc) in parent:
                    count-=union((r,c),(nr,nc))
            res.append(count)
        return res

Java

class Solution {
    int[] parent, rank;
    int find(int x){ return parent[x]==x?x:(parent[x]=find(parent[x])); }
    int union(int a, int b){
        a=find(a); b=find(b);
        if(a==b) return 0;
        if(rank[a]<rank[b]){int t=a;a=b;b=t;}
        parent[b]=a; if(rank[a]==rank[b]) rank[a]++;
        return 1;
    }
    public List<Integer> numIslands2(int m, int n, int[][] pos){
        parent=new int[m*n]; rank=new int[m*n];
        Arrays.fill(parent,-1);
        List<Integer> res=new ArrayList<>(); int cnt=0;
        int[][] dirs={{0,1},{0,-1},{1,0},{-1,0}};
        for(int[] p:pos){
            int r=p[0],c=p[1],idx=r*n+c;
            if(parent[idx]!=-1){res.add(cnt);continue;}
            parent[idx]=idx; cnt++;
            for(int[] d:dirs){
                int nr=r+d[0],nc=c+d[1],ni=nr*n+nc;
                if(nr>=0&&nr<m&&nc>=0&&nc<n&&parent[ni]!=-1) cnt-=union(idx,ni);
            }
            res.add(cnt);
        }
        return res;
    }
}

Complexity

Time: O(k * α(mn)) | Space: O(mn)