# Can we solve this using unordered map?

• I have used unordered map as shown below for solving this. C++ reference says that the avg. time complexity for retrieval, insertion and searching in unordered map is constant. So the avg. time complexity of this solution is also linear. Thoughts?

``````#include<unordered_map>

class Solution {
public:
int longestConsecutive(vector<int> &num) {
std::unordered_map<int,vector<int>>map;
int max=0;
for(int i=0;i<num.size();i++){
if(map.count(num[i])>0)continue;
vector<int>maxmin_l;
vector<int>maxmin_r;
if(map.count(num[i]-1)==1)maxmin_l=map[num[i]-1];
if(map.count(num[i]+1)==1)maxmin_r=map[num[i]+1];
int l,r;
if(maxmin_l.size()==2 and maxmin_r.size()==2){
l=maxmin_l[1]-maxmin_l[0]+1;
r=maxmin_r[1]-maxmin_r[0]+1;
vector<int>temp;
temp.push_back(maxmin_l[0]);
temp.push_back(maxmin_r[1]);
map[num[i]]=temp;
vector<int>temp2=map[maxmin_l[0]];
vector<int>temp3=map[maxmin_r[1]];
temp2[1]=maxmin_r[1];
temp3[0]=maxmin_l[0];
map[maxmin_l[0]]=temp2;
map[maxmin_r[1]]=temp3;
}else if(maxmin_l.size()==2){
vector<int>temp;
temp.push_back(maxmin_l[0]);
temp.push_back(num[i]);
map[num[i]]=temp;
l=maxmin_l[1]-maxmin_l[0]+1;
r=0;
vector<int>temp1=map[maxmin_l[0]];
temp1[1]=num[i];
map[maxmin_l[0]]=temp1;
}else if(maxmin_r.size()==2){
vector<int>temp;
temp.push_back(num[i]);
temp.push_back(maxmin_r[1]);
map[num[i]]=temp;
r=maxmin_r[1]-maxmin_r[0]+1;
l=0;
vector<int>temp2=map[maxmin_r[1]];
temp2[0]=num[i];
map[maxmin_r[1]]=temp2;
}else{
vector<int>temp;
temp.push_back(num[i]);
temp.push_back(num[i]);
map[num[i]]=temp;
l=0;
r=0;
}
if(l+r+1>max)max=l+r+1;
}
return max;
}
};``````

• I have a simpler solution, that uses unordered_map, but two unordered_map<int, int>. They link the beginning to the end of each sequence and the otherway around.

At each iteration I create a sequence of one value and I try to merge with a sequence just before and just after, then I inserted the new sequence into the two hash maps.

class Solution {

public:

``````int longestConsecutive(vector<int> &num) {

if (num.empty()) return 0;

unordered_map<int, int> mapFL; // Hash map that links first -> last
unordered_map<int, int> mapLF; // Hash map that links last -> first

int maxConsecutive = 1;

for (int val: num) {

// We represent each sequence as [first,last)
int first = val;
int last = val + 1;

// Looks if the current element is duplicated:
if (mapFL.find(first) != end(mapFL)) continue;
if (mapLF.find(last) != end(mapLF)) continue;

// Is first also last of another sequence?
auto itLF = mapLF.find(first);
if (itLF != end(mapLF)) {
// YES! Merges the 2 sequences.
first = itLF->second;
mapLF.erase(itLF);
}

// Is last also first of another sequence?
auto itFL = mapFL.find(last);
if (itFL != end(mapFL)) {
// YES! Merges the 2 sequences.
last = itFL->second;
mapFL.erase(itFL);
}

// Saves the merged sequence:
mapFL[first] = last;
mapLF[last] = first;

// If the last processed sequence is the biggest, accounts its size:
maxConsecutive = max(maxConsecutive, last - first);
}

return maxConsecutive;
}
``````

};

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