# C++ code: idea & code

• 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);
}
}

};``````

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