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.

Longest Consecutive Sequence.cpp

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int, int> map;
        int res = 1;
        for(int i = 0; i < num.size(); ++i) {
            int cur = num[i];
            if(map.find(cur) != map.end()) {
                continue;
            } else {
                
                map[cur] = 1;
                //checking left
                unordered_map<int, int>::iterator left = map.find(cur - 1);
                if(left != map.end()) {
                    res = max(res, merge(map, cur - 1));
                    
                } 
                //checking right
                unordered_map<int, int>::iterator right = map.find(cur + 1);
                if(right != map.end()) {
                    res = max(res, merge(map, cur));
                }
            }
            
            
        }
        return res;

    }
    
    
    int merge(unordered_map<int, int>& map, int left) {
        unordered_map<int, int>::iterator llower, lupper, rlower, rupper;
        lupper = map.find(left);
        llower = map.find((*lupper).first - (*lupper).second + 1);
        rlower = map.find(left + 1);
        rupper = map.find((*rlower).first + (*rlower).second - 1);
        int len = (*llower).second + (*rupper).second;
        (*llower).second = (*rupper).second = len;
        return len;
    }
};