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.