My Java Solution using UnionFound


  • 35
    S
    public class Solution {
            public int longestConsecutive(int[] nums) {
                UF uf = new UF(nums.length);
                Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
                for(int i=0; i<nums.length; i++){
                    if(map.containsKey(nums[i])){
                        continue;
                    }
                    map.put(nums[i],i);
                    if(map.containsKey(nums[i]+1)){
                        uf.union(i,map.get(nums[i]+1));
                    }
                    if(map.containsKey(nums[i]-1)){
                        uf.union(i,map.get(nums[i]-1));
                    }
                }
                return uf.maxUnion();
            }
        }
        
        class UF{
            private int[] list;
            public UF(int n){
                list = new int[n];
                for(int i=0; i<n; i++){
                    list[i] = i;
                }
            }
            
            private int root(int i){
                while(i!=list[i]){
                    list[i] = list[list[i]];
                    i = list[i];
                }
                return i;
            }
            
            public boolean connected(int i, int j){
                return root(i) == root(j);
            }
            
            public void union(int p, int q){
              int i = root(p);
              int j = root(q);
              list[i] = j;
            }
            
            // returns the maxium size of union
            public int maxUnion(){ // O(n)
                int[] count = new int[list.length];
                int max = 0;
                for(int i=0; i<list.length; i++){
                    count[root(i)] ++;
                    max = Math.max(max, count[root(i)]);
                }
                return max;
            }
        }

  • 0
    L

    Very good idea! But I think the complexity of union-find is o(nlogn), right?


  • 5
    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, @liangyue268 Weighted Union Find with Path Compression isn't exactly O(nlogn) but more 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; }
        }
    }
    

  • 4

    My Union find code from Princeton Algo. class

    class Union_Find{
    public:
        Union_Find (int N) {
            for (int i = 0; i < N; i++) {
                id.push_back(i);
                sz.push_back(1);
            }
        }
    
        void Union(int A, int B) {
            int rootA = Find(A);
            int rootB = Find(B);
            if (rootA == rootB) return;
            if (sz[rootA] < sz[rootB]) {
                id[rootA] = rootB;
                sz[rootB] += sz[rootA];
            } else {
                id[rootB] = rootA;
                sz[rootA] += sz[rootB];
            }
        }
    
        int Find(int p) {
            while (p != id[p]) {
                id[p] = id[id[p]];
                p = id[p];
            }
            return p;
        }
    
        int maxSize() {
            int res = 0;
            for (auto s : sz)
                res = max(res, s);
            return res;
        }
        
    private:
        vector<int> id;
        vector<int> sz;
    };
    
    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            Union_Find uf(nums.size());
            unordered_map<int, int> mapIndex;
            for (int i = 0; i < nums.size(); i++) {
                if (mapIndex.count(nums[i])) continue; // in case of duplicate
                mapIndex.insert(make_pair(nums[i], i));
                
                if (mapIndex.count(nums[i] + 1)) {
                    uf.Union(i, mapIndex[nums[i] + 1]);
                }
                if (mapIndex.count(nums[i] - 1)) {
                    uf.Union(i, mapIndex[nums[i] - 1]);
                }
            }
            return uf.maxSize();
        }
    };
    

  • 0

    @liangyue268
    More precisely, the UF algorithm with path compression and ranked union is O(N+M log*N), where M is the number of UF operations (union and find), N is number of objects. log*N is a very slow growing function, which can be regarded as constant.

    But the solution posted does not apply the ranked union mechanism, which makes its complexity be O(MlogN). And for the problem, M = O(N), thus the posted solution's complexity is O(NlogN). Yeah, you are right :)

    Reference: Princeton lecture notes, page 31 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf


  • 0
    public int longestConsecutive2(int[] nums) {
        int n = nums.length;
        UnionFind uf = new UnionFind(n);
    
        Map<Integer, Integer> map = new HashMap<>(); 
        for (int i = 0; i < n; i++) map.put(nums[i], i);
    
        for (int num : nums)
            if (map.containsKey(num+1))
                uf.union(map.get(num), map.get(num+1));
    
        return uf.getMaxSize();
    }
    
    private class UnionFind {
        private int[] id;
        private int[] sz;
        private int maxSize;
    
        public UnionFind(int n) {
            id = new int[n];
            sz = new int[n];
            for (int i = 0; i < n; i++) {
                id[i] = i;
                sz[i] = 1;
            }
            maxSize = n > 0 ? 1 : 0;
        }
    
        public int findRoot(int i) {
            if (i == id[i])  return i;
            id[i] = findRoot(id[i]);
            return id[i];
        }
    
        public void union(int p, int q) {
            int rootP = findRoot(p);
            int rootQ = findRoot(q);
    
            if (rootP == rootQ)  return;
            if (sz[rootP] < sz[rootQ]) {
                id[rootP] = rootQ;
                sz[rootQ] += sz[rootP];
                maxSize = Math.max(maxSize, sz[rootQ]);
            } else {
                id[rootQ] = rootP;
                sz[rootP] += sz[rootQ];
                maxSize = Math.max(maxSize, sz[rootP]);
            }
        }
    
        public int getMaxSize() {
            return this.maxSize;
        }
    }

  • 0
    S

    O(log*N) is basically considered as constant. For Union and Find, if you do path compression, you will have O(log*N), so this solution is indeed O(n).


Log in to reply
 

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