I have a simple solutiion that passes the test:

```
class Solution {
public:
int longestConsecutive(vector<int> &num) {
if (num.empty()) return 0;
set<int> set(begin(num), end(num));
auto it = set.begin();
int prev = *it;
int numConsecutive = 1;
int maxConsecutive = 1;
for (++it; it != set.end(); ++it) {
int current = *it;
if (current == prev + 1) {
numConsecutive++;
}
else {
maxConsecutive = max(maxConsecutive, numConsecutive);
numConsecutive = 1;
}
prev = current;
}
return max(maxConsecutive, numConsecutive);
}
};
```

The solution uses a set. It is not O(n) because every insertion if O(log(N)). The solution is

O(N log(N)).

A solution involving an hash map has the same problem, is O(N^2) in case num contains only identical elements.

Bucket sort, that is O(N), doesn't work because requires a small set of elements (and there is a specific test case passing INT_MAX and INT_MIN beside the values of the array.

So I'm seriously interested now to know what is the O(n) solution.