Amazon — Number of Islands II (Union-Find Dynamic)

3×3 grid
add (0,0) → 1 island
add (0,1) → 1 island (merged)
add (1,2) → 2 islands
add (1,1) → 1 island (merged all)

class Solution:
    def numIslands2(self, m, n, positions):
        parent = {}
        rank = {}
        count = 0

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

        def union(x, y):
            nonlocal count
            px, py = find(x), find(y)
            if px == py: return
            if rank.get(px, 0) < rank.get(py, 0):
                px, py = py, px
            parent[py] = px
            if rank.get(px, 0) == rank.get(py, 0):
                rank[px] = rank.get(px, 0) + 1
            count -= 1

        res = []
        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:
                    union((r,c), (nr,nc))
            res.append(count)
        return res

function numIslands2(m, n, positions) {
    const parent = new Map(), rank = new Map();
    let count = 0;
    const find = (x) => { if (parent.get(x)!==x) parent.set(x,find(parent.get(x))); return parent.get(x); };
    const union = (x,y) => {
        const [px,py]=[find(x),find(y)]; if(px===py)return;
        const [rx,ry]=[rank.get(px)||0,rank.get(py)||0];
        if(rx<ry)parent.set(px,py); else if(rx>ry)parent.set(py,px);
        else{parent.set(py,px);rank.set(px,rx+1);}
        count--;
    };
    const res=[];
    for (const [r,c] of positions) {
        const k=r+','+c;
        if(!parent.has(k)){parent.set(k,k);rank.set(k,0);count++;}
        for(const[dr,dc]of[[-1,0],[1,0],[0,-1],[0,1]]){
            const nk=(r+dr)+','+(c+dc);
            if(parent.has(nk))union(k,nk);
        }
        res.push(count);
    }
    return res;
}

import java.util.*;
public List<Integer> numIslands2(int m, int n, int[][] pos) {
    Map<Integer,Integer> parent=new HashMap<>(), rank=new HashMap<>();
    int[] count={0}; List<Integer> res=new ArrayList<>();
    int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}};
    for (int[] p : pos) {
        int id=p[0]*n+p[1];
        if (!parent.containsKey(id)){ parent.put(id,id); rank.put(id,0); count[0]++; }
        for (int[] d:dirs){
            int nr=p[0]+d[0],nc=p[1]+d[1],nid=nr*n+nc;
            if (nr>=0&&nr<m&&nc>=0&&nc<n&&parent.containsKey(nid)){
                int px=find(parent,id),py=find(parent,nid);
                if(px!=py){int rx=rank.get(px),ry=rank.get(py);if(rx<ry){int t=px;px=py;py=t;}parent.put(py,px);if(rx==ry)rank.merge(px,1,Integer::sum);count[0]--;}
            }
        }
        res.add(count[0]);
    }
    return res;
}
int find(Map<Integer,Integer> p, int x){ if(p.get(x)!=x)p.put(x,find(p,p.get(x)));return p.get(x);}

#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
    unordered_map<int,int> par, rk;
    int cnt=0;
    int find(int x){ return par[x]==x?x:par[x]=find(par[x]); }
    void unite(int x,int y){ int px=find(x),py=find(y); if(px==py)return; if(rk[px]<rk[py])swap(px,py); par[py]=px; if(rk[px]==rk[py])rk[px]++; cnt--; }
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& pos) {
        vector<int> res; int dirs[]={-1,0,1,0,-1};
        for (auto& p:pos) {
            int id=p[0]*n+p[1];
            if(!par.count(id)){par[id]=id;rk[id]=0;cnt++;}
            for (int d=0;d<4;d++){int nr=p[0]+dirs[d],nc=p[1]+dirs[d+1],nid=nr*n+nc;if(nr>=0&&nr<m&&nc>=0&&nc<n&&par.count(nid))unite(id,nid);}
            res.push_back(cnt);
        }
        return res;
    }
};

/* C: array-based union-find with path compression + union by rank */