LeetCode : 305. Number of Islands II

O(k log mn), where k is the length of the positions.
UnionFind
class Solution {
    class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];

            for(int i = 0; i< n ; i++) parent[i] = i;
        }

        boolean union(int x, int y) { // already unioned? return false
            if (x == y) return false;

            int xRoot = findParent(x);
            int yRoot = findParent(y);
            if (xRoot == yRoot) return false;

            if (rank[xRoot] < rank[yRoot]) parent[xRoot] = yRoot;
            else if (rank[xRoot] > rank[yRoot]) parent[yRoot] = xRoot;
            else {
                parent[yRoot] = xRoot;
                rank[xRoot]++;
            }

            return true;
        }

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

    int[] dx = {-1,0,1,0};
    int[] dy = {0,-1,0,1};

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        UnionFind uf = new UnionFind(m*n);
        Set<Integer> set = new HashSet();
        List<Integer> list = new ArrayList();
        int num = 0;

        for (int i = 0; i < positions.length; i++) {
            int[] p = positions[i];
            int cur = p[0] * n + p[1];
            set.add(cur);
            num++; // by default, add one isolated island.

            for (int d = 0; d < 4; d++) {
                int ny = p[0] + dy[d], nx = p[1] + dx[d];
                if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue; // outside

                int pre = ny * n + nx;
                if (set.contains(pre) && uf.union(cur, pre))  // already united one
                    num--; // !!! do not decrease if it's already united here
            }        

            list.add(num);
        }

        return list;
    }
}
congr / world

LeetCode : 305. Number of Islands II #484
