# Finally accepted using two unordered map with complexity O(n)

• I use two maps to keep the numbers from ascending and descending order. In fact, I think these two maps can be merged into one. But that would be much more difficult to understand

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_map<int,int> seq;     //lower to higher
unordered_map<int,int> seq2;    //higher to lower
int maxlen = 0;
for(int i=0;i<num.size();i++){
unordered_map<int,int>::iterator it;
unordered_map<int,int>::iterator it2;
it = seq.find(num[i]);
it2 = seq2.find(num[i]);
if(it != seq.end() || it2 != seq2.end()){
continue;
}
it = seq.find(num[i]+1);    //find if num[i] can be lower
it2 = seq2.find(num[i]-1);  //find if num[i] can be higher
if(it != seq.end() && it2 != seq2.end()){ //if there are two sequences that can be merged together
int high = it->second;
int low = it2->second;
seq.erase(it);
seq.erase(low);
seq2.erase(high);
seq2.erase(it2);
seq.insert(pair<int,int>(low,high));
seq2.insert(pair<int,int>(high,low));
maxlen = maxlen > high-low+1 ? maxlen : high-low+1;
}
else if(it != seq.end()){
int high = it->second;
seq.erase(it);
seq2.erase(high);
seq.insert(pair<int,int>(num[i],high));
seq2.insert(pair<int,int>(high,num[i]));
maxlen = maxlen > high-num[i]+1 ? maxlen : high-num[i]+1;
}
else if(it2 != seq2.end()){
int low = it2->second;
seq2.erase(it2);
seq.erase(low);
seq.insert(pair<int,int>(low,num[i]));
seq2.insert(pair<int,int>(num[i],low));
maxlen = maxlen > num[i]-low+1 ? maxlen : num[i]-low+1;
}
else{
seq.insert(pair<int,int>(num[i],num[i]));
seq2.insert(pair<int,int>(num[i],num[i]));
maxlen = maxlen > 1 ? maxlen : 1;
}
}
return maxlen;
}
};``````

My solution 52 ms

• Sadly my runtime is 128ms

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