class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        DisjointSetUnion dsu = new DisjointSetUnion(positions.length);
        HashMap<Point, Integer> map = new HashMap<>();
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < positions.length; i++) {
            Point p = new Point(positions[i][0], positions[i][1]);
            if (!map.containsKey(p)) {
                dsu.numSets++;
                map.put(p, i);
            }
            unionNeighbours(positions, i, dsu, map);
            list.add(dsu.numSets);
        }
        return list;
    }

    void unionNeighbours(int[][] positions, int i, DisjointSetUnion dsu, HashMap<Point, Integer> map) {
        Point p = new Point(positions[i][0], positions[i][1]);
        Point n = new Point(positions[i][0], positions[i][1]);
        n.x++;
        if (map.containsKey(n)) dsu.union(map.get(p), map.get(n));
        n.x--;
        n.y++;
        if (map.containsKey(n)) dsu.union(map.get(p), map.get(n));
        n.y -= 2;
        if (map.containsKey(n)) dsu.union(map.get(p), map.get(n));
        n.y++;
        n.x--;
        if (map.containsKey(n)) dsu.union(map.get(p), map.get(n));
    }

    class DisjointSetUnion {
        int[] parent, rank;
        int numSets;
        public DisjointSetUnion(int n) {
            numSets = 0;
            rank = new int[n];
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot != yRoot) {
                numSets--;
                if (rank[xRoot] > rank[yRoot]) parent[yRoot] = xRoot;
                else {
                    parent[xRoot] = yRoot;
                    if (rank[xRoot] == rank[yRoot]) rank[yRoot]++;
                }
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }

    class Point {
        int x, y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object obj) {
            Point p = (Point) obj;
            return x == p.x && y == p.y;
        }
        @Override
        public int hashCode() {
            return x + y;
        }
    }
}