Java commented Union-Find with Path Compression Solution


  • 0
    L

    I implemented the following code which is a slight improvement over the one suggested in the original post. I have optimized the retrieval of the maxUnion (getHighestRank in my case) to O(1).

    Also, Weighted Union Find with Path Compression is close to O(n). This is because the path compression function (see find operation) exhibits growth which follows the Inverse Ackermann Function. Both union and find are not exactly 1 but are very very very close to 1, visit here for more details.

    import java.util.Map;
    import java.util.HashMap;
    
    public class Solution {
        public int longestConsecutive(int[] nums) {
            final int length = nums.length;
            if (length <= 1) return length;
            
            final Map<Integer, Integer> elementIndexMap = new HashMap();
            final UnionFind uf = new UnionFind(length);
            for (int p = 0; p < length; p++) {
                final int i = nums[p];
                if (elementIndexMap.containsKey(i)) continue;
                if (elementIndexMap.containsKey(i+1)) uf.union(p, elementIndexMap.get(i+1));
                if (elementIndexMap.containsKey(i-1)) uf.union(p, elementIndexMap.get(i-1));
                elementIndexMap.put(i, p);
            }
            return uf.getHighestRank();
        }
        
        private final class UnionFind {
            final private int[] sequenceTree;
            final private int[] rank;
            private int highestRank;
            
            UnionFind(int length) {
                sequenceTree = new int[length];
                rank = new int[length];
                highestRank = 1;
                for (int i = 0; i < length; i++) {
                    sequenceTree[i] = i;
                    rank[i] = 1;
                }
            }
            
            void union(int p, int q) {
                final int pId = find(p); final int qId = find(q);
                
                if (pId == qId) return;
                
                int localHighestRank = 1;
                if (rank[pId] < rank[qId]) {
                    sequenceTree[pId] = qId;
                    rank[qId] += rank[pId];
                    localHighestRank = rank[qId];
                } else {
                    sequenceTree[qId] = pId;
                    rank[pId] += rank[qId];
                    localHighestRank = rank[pId];
                }
                highestRank = Math.max(highestRank, localHighestRank);
            }
            
            int find(int p) {
                while (p != sequenceTree[p]) {
                    sequenceTree[p] = sequenceTree[sequenceTree[p]];
                    p = sequenceTree[p];
                }
                return p;
            }
            
            int getHighestRank() { return highestRank; }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.