Simplest CPP O(n) solution using hashing


#1

int Solution::longestConsecutive(const vector &A) {
map<int,int> x;
for(int i=0;i<A.size();i++)
x[A[i]]=1;
int ans=1;
int z=1;
for(auto itr=x.begin();itr!=x.end();itr++)
{
if(itr!=x.begin()){
if((itr–)->first-1==(itr++)->first)
{
z++;
ans=max(ans,z);
}
else
z=1;}
}
return ans;
}


#2

This is not O(n). Map uses redblack trees for implementation. It takes log n to insert and delete. Hence inserting keys in a map is equivalent to sorting