305.Number of Islands II

https://leetcode.com/problems/number-of-islands-ii/discuss/75470

UNIONoperation is only changing the root parent so the running time isO(1).

FINDoperation is proportional to the depth of the tree. If N is the number of points added, the average running time isO(logN), and a sequence of4Noperations takeO(NlogN). If there is no balancing, the worse case could beO(N^2).

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        if(m <= 0 || n <= 0)
            return ans;
        int[][] dirs = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        int[] roots = new int[m * n];
        int cntOfIslands = 0;
        Arrays.fill(roots, -1);
        for(int[] pos : positions){
            // assume new point is isolated island
            int id = n * pos[0] + pos[1];
            int currentRoot = id;
            roots[id] = currentRoot;

            cntOfIslands += 1;
            for(int[] dir : dirs){
                int x = pos[0] + dir[0];
                int y = pos[1] + dir[1];
                int neighborID = n * x + y;
                if(x < 0 || x >=m || y < 0 || y >= n ||  roots[neighborID] == -1)
                    continue;
                int neighborRoot = findRoot(roots, neighborID);
                // if neighbor is in another island
                if(id != neighborRoot){
                    roots[currentRoot] = neighborRoot;
                    currentRoot = neighborRoot;
                    cntOfIslands--;
                }
            }
            ans.add(cntOfIslands);
        }
        return ans;
    }
    public int findRoot(int[] roots, int id){
        while(id != roots[id]){
            roots[id] = roots[roots[id]];
            id = roots[id];
        }
        return id;
    }
}