C++ code: idea & code


  • 0
    J

    Idea: disjoint sets using forests with path compression. T(n) = O(n)

    class Solution {
    private:
        typedef pair<int, int> PR;
        #define mkp make_pair
        unordered_map<int, int> parent;
        unordered_map<int, int> level;
        unordered_map<int, PR> range;
        int ret;
    public:
        int longestConsecutive(vector<int>& nums) {
            int n = nums.size();
            if (n < 2)  //simple case
                return n;
            ret = 1;
            for (int i = 0; i < n; i++) {
                int a = nums[i];
                if (parent.count(a))    continue; //it has been processed
                parent[a] = a;
                level[a] = 0;
                range[a] = mkp(a, a);
                for (int d = -1; d < 2; d += 2) { //predecessor and successor
                    int b = a + d;
                    if (parent.count(b)) {
                        mergeRange(a, b);
                    }
                }
            }
            return ret;
        }
        
        int getParent(int a) {
            if (parent[a] == a)
                return a;
            parent[a] = getParent(parent[a]);
            return parent[a];
        }
        
        void mergeRange(int a, int b) {
            int pa = getParent(a), pb = getParent(b);
            if (pa != pb) {
                int lo = min(range[pa].first, range[pb].first);
                int hi = max(range[pa].second, range[pb].second);
                if (level[pa] >= level[pb]) {
                    if (level[pa] == level[pb])
                        level[pa]++;
                    parent[pb] = pa;
                    range[pa] = mkp(lo, hi);
                } else {
                    parent[pa] = pb;
                    range[pb] = mkp(lo, hi);
                }
                ret = max(ret, hi-lo+1);
            } 
        }
        
    };

Log in to reply
 

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