### [Longest Consecutive Sequence]

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given `[100, 4, 200, 1, 3, 2]`

,

The longest consecutive elements sequence is `[1, 2, 3, 4]`

. Return its length: `4`

.

Your algorithm should run in O(*n*) complexity.

### [Analysis]

In O(n) we can’t do a sort. Given O(n), what we can do is to scan through the array. Note that we also need to retain elements which are not sorted and thus not stored in order. We need to retrieve elements in order and it must be a O(1) operation to retrieve the “next” and the “previous” element of a given one. What comes to mind? **Hashmap!**

int longestConsecutive(vector<int> &num) { if (num.empty()) return 0; unordered_set<int> hm; for (int i=0; i<num.size(); ++i) { hm.emplace(num[i]); } int max = 0; for (int e : num) { int c = 1; int left = e-1, right = e+1; while (hm.find(left)!=hm.end()) { c++; hm.erase(left); left--; } while (hm.find(right)!=hm.end()) { c++; hm.erase(right); right++; } max = std::max(c, max); } return max; }

Advertisements