# A C++ Solution using Union Find

• ``````/**
* 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){
}

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;
}
};
``````

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