## 128. Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

Example:

``````Input:
[100, 4, 200, 1, 3, 2]

Output:
4

Explanation:
The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
``````

Thoughts:

m[k] -> length for key k,

m[k] == m[k-1] + m[k+1]; m[]

keep expanding the boundary by looking up neighbor value and update the boundary point records

Code O(n)

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans = 0;
unordered_map <int, int> m;
for(int n : nums){
if(m.find(n)== m.end()){
// must first lookup then get the value, otherwise the map will put an default KV pair
int left = (m.find(n-1)!= m.end())?m[n-1]:0, right = (m.find(n+1)!= m.end())?m[n+1]:0,
sum = left + 1 + right;
ans = max(ans, sum);

// update
m[n] = sum;
m[n - left] = sum;
m[n + right] = sum;

}
}

return ans;
}
};
``````

Thanks 's dchen0215 's answer.