C++ UNION_FIND almost O(n) 9ms, beats over 80%.

• ``````class Solution {
private:
vector<int> id;
vector<int> size; // the depth for each element
int ans; // the final ans
public:
int Find(int i){
while(i != id[i]){
id[i] = id[id[i]]; // path compression, make it close to O(1) :)
i = id[i];
}
return i;
}
void Union(int i, int j){
int rootx = Find(i);
int rooty = Find(j);
if(rootx != rooty){
id[rooty] = rootx;
size[rootx] += size[rooty]; // update the depth
ans = max(ans, size[rootx]);
}
}
int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0){
return 0;
}
unordered_map<int,int> m; // val -> index
ans = 1;  // at least 1 if not empty
id = vector<int>(nums.size(), 0);
for(int i = 0; i< nums.size();i++){
id[i] = i;
}
size = vector<int>(nums.size(), 1);
for(int i = 0; i< nums.size(); i++){
if(m.find(nums[i]) == m.end()){
m[nums[i]] = i;
if(m.find(nums[i]-1) != m.end()){
Union(i, m[nums[i]-1]);
}
if(m.find(nums[i]+1) != m.end()){
Union(i, m[nums[i]+1]);
}
}
}
return ans;
}
};
``````

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