A C++ Solution using Union Find


  • 0
    G
    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
    class SummaryRanges {
    public:
        /** Initialize your data structure here. */
        
        struct UFNode{
            UFNode *parent;
            int min;
            int max;
            int size;
            
            UFNode(int min,int max):
                parent(nullptr),
                min(min),
                max(max),
                size(1){}
            
            UFNode():
                parent(nullptr),
                size(1){}
            
        };
        
        UFNode *find(UFNode *n){
            
            if(n->parent == nullptr){
                return n;
            }
            
            n->parent = find(n->parent);
            return n->parent;
        }
        
        void unionTwoNodes(UFNode *n1, UFNode *n2){
            
            UFNode *r1 = find(n1);  
            UFNode *r2 = find(n2);
            
            if(r1 == r2){
                return;
            }
    
            int size1 = r1->size;
            int size2 = r2->size;
            
            if(r1->size > r2->size){
                r2->parent = r1;
                r1->size += r2->size;
                r1->min = min(r1->min,r2->min);
                r1->max = max(r1->max,r2->max);
            }
            else{
                r1->parent = r2;
                r2->size += r1->size;
                r2->min = min(r2->min,r1->min);
                r2->max = max(r2->max,r1->max);
            }
        }
        
        //member variables
        unordered_map<int,UFNode*> m;
        int minNum;
        int maxNum;
        
        SummaryRanges():
        minNum(INT_MAX),
        maxNum(INT_MIN){
        }
        
        void addNum(int val) {
        
            if(m.find(val) != m.end()){
                return;
            }
            
            UFNode *node = new UFNode(val,val);
            m[val] = node;
            minNum = min(minNum,val);
            maxNum = max(maxNum,val);
            
            if(m.find(val - 1) != m.end()){
                unionTwoNodes(node,m[val - 1]);
            }
            
            if(m.find(val + 1) != m.end()){
                unionTwoNodes(node,m[val + 1]);
            }
        }
        
        vector<Interval> getIntervals() {
            
            vector<Interval> result;
            
            for(int i = minNum; i <= maxNum;){
                
                if(m.find(i) == m.end()){
                    i++;
                    continue;
                }
                
                auto node = m[i];
                
                if(node->parent != nullptr){
                    node = find(node);
                }
                
                Interval intv(node->min,node->max);
                result.push_back(intv);
                
                i = node->max + 1;
            }
            
            return result;
        }
    };
    

Log in to reply
 

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