# I think the problem is not well formulated.

• 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.

• This post is deleted!

• I was wrong about hash maps.

Here you can see my second solution using two of them. O(n). ;-)

``````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;
}
};``````

• Hello, an unordered_set is used as the hash table in my case. It is O(N) because each element is only scanned once. For the 1st element (beginning of the set), I search its neighbors in two directions until it fails to find any. Erase all neighbors found from the set, also this element at the end. In this way, a single sequence is scanned and erased. Go to next element (still the beginning of the set), and repeat the process.

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
if (num.size() == 0)
return 0;

// for each element in the set, search to left and right
// remove this element and all its found neighbors from the set
// stop when search failed on each direction
// each element is only scanned exactly one time
// so the overall complexity is O(N)
int maxL = 1;
int curL = 1;
unordered_set<int> keys(num.begin(), num.end());
while(!keys.empty()) {
auto cur = keys.begin();
int i1 = *cur;
while (!keys.empty()) { // search to right
auto it = keys.find(++i1);
if (it != keys.end()) {
curL++;
keys.erase(it);
}
else {
break;
}
}

i1 = *cur;
while (!keys.empty()) { // search to left
auto it = keys.find(--i1);
if (it != keys.end()) {
curL++;
keys.erase(it);
}
else {
break;
}
}
keys.erase(cur);

if (curL > maxL)
maxL = curL;
curL = 1;
}
return maxL;
}
};``````

• Yes my second commentary is confirmin your solution. Just my second solution may be faster because does everything on place with only one passage but can be improved a lot catching consecutive numbers if the sequence is not completely unsorted.

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