# O(n) time and O(n) space C++ solution in less than 20 lines

• The idea here is to create a map of element [ i ] ==> length of consecutive sequence upto element i .
The answer would simply be the maximum value of second element of the map.
Again we all are assuming map lookups are in O(1) .

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
map<int,int> mp;
for(int i=0;i<num.size();++i)
mp[num[i]] = 1;
for(map<int,int>::iterator i=mp.begin();i!=mp.end();++i){
if(mp.find(i->first-1) != mp.end()){
i->second = mp[i->first-1]+1;
}
}
int ans=0;
for(map<int,int>::iterator i=mp.begin();i!=mp.end();++i){
ans = max(ans,i->second);
}
return ans;
}
};``````

• Nice! But there might be a small problem that's easy to fix.

It seems to me that this would only work if map stores entries in ascending order, which would make it O(nlogn) instead of O(n).

• What's the run time?
My solution is 52ms

• I think your solution costs O(nlogn) in time.

• The map's insert operation is O(lgn), so your solution is O(nlgn)

• I agree with you, this method only works if map stores entries(first value) in ascending order;But you must attention that the key value of the map is sorted from small to large by using red-black tree. So this solving method is right.

• Just switch from map to unordered_map

• The solution depends on the map to have the numbers ordered when you iterate through it. So you can't use unordered_map.

• map<T, T> in c++ is a tree structure which has a O(logn) complexity. The hash map in C++11 is unordered_map

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