• I have seen a lot of discussion about this problem.In my opinion,it is not correct to use set(which is ordered),because very time we insert an element to a ordered set,it will cost O(n),so the total complexity is O(nlogn),which violates the request of the problem.So here we use an unordered_set,and one is enough.

Besides,to think about this problem,one principle issue we should realize is that usually when we want to reduce the time complexity,we have to increase the space complexity.In this case,if we want to access an element within O(1),we have to use hash table.

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_set<int> record(num.begin(),num.end());
int res = 1;
for(int n : num){
if(record.find(n)==record.end()) continue;
record.erase(n);
int prev = n-1,next = n+1;
while(record.find(prev)!=record.end()) record.erase(prev--);
while(record.find(next)!=record.end()) record.erase(next++);
res = max(res,next-prev-1);
}
return res;
}
};``````

• This code is referenced to grapeot's code.

• This post is deleted!

• nice solution, thanks for sharing

• Nice idea! Rather than use `set<int>`. +1 vote

• I found that the worst case look up time of unordered_set is still n (unordered_set on cppreference.com). Therefore, I still concern that the algorithm may have O(n^2) since we need to call `unordered_set::find()` for each element of the array. I actually came up with the same algorithm with the unordered_set.

I guess the best way is to use a hash table backed by std::vector which always has constant look up time (vector on cppreference.com).

• Very elegant idea and code!

• unordered_set::find() cost only O(1)

• Insert an element into a ordered set will cost O(log(n)). Ordered set is based or RB-tree.

• @wang.shuai.750
Isn't be O(logn) for insert once in ordered set?

• @wang.shuai.750 brilliant!!!! thanks!

• Do we not need to handle integer overflow?
What's expected answer for the following input?
Input: [2147483647,-2147483648]

• You are incredible!

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