Day 68, #128, Longest Consecutive Sequence

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.
----------------------------------------------------------------------------
O(n),using a hash to map an integer and its number of consecutive integers found so far, initialized as 0
3 scenarios we have to tackle:
1) found connecting number on both left and right sides, attach 2 segments together
2) only the right
3) only the left

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int,int> mapping;
        int maxLen = 0;
        for (int i = 0; i < num.size(); i++) {
            int key = num[i]; 

            // skip duplicates
            if (mapping.find(key) == mapping.end()) {
                mapping[key] = 0;
            }else continue;
            
            if (mapping.find(key - 1) != mapping.end() && mapping.find(key + 1) != mapping.end() ) {
                int left = key - 1 - mapping[key - 1]; // find index of the left most number on current segment
                int right = key + 1 + mapping[key + 1]; // find index of the rightmost number on current segment
                mapping[left] += 2 + mapping[right]; // watch out for 2 
                mapping[right] = mapping[left];
                maxLen = max(mapping[left],maxLen);
            }else if (mapping.find(key - 1) != mapping.end()) {
                int left = key - 1 - mapping[key - 1];
                mapping[left]++;
                mapping[key] = mapping[left];
                maxLen = max(mapping[left],maxLen);
            }else if (mapping.find(key + 1) != mapping.end() ) {
                int right = key + 1 + mapping[key + 1];
                mapping[right]++;
                mapping[key] = mapping[right];
                maxLen = max(mapping[right],maxLen);
            }
        }
        return maxLen + 1;
    }
};

Update Nov-23-2014
Another approach

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int,bool> mapping;
        for (int i = 0; i < num.size(); i++) {
            mapping[num[i]] = true;
        }
        
        int longest = 0;
        for (int i = 0; i < num.size(); i++) {
            if (!mapping[num[i]]) continue;
            mapping[num[i]] = false;
            int left = num[i] - 1, right = num[i] + 1;
            int length = 1;
            
            while (mapping[left] || mapping[right]) {
                if (mapping[left]) {
                    mapping[left] = false;
                    length++;
                    left--;
                }
                if (mapping[right]) {
                    mapping[right] = false;
                    length++;
                    right++;
                }
            }
            
            longest = max(longest,length);
        }
        
        return longest;
    }
};

变种题：array可能变为tree，对于无重复的可以只记录范围，来节省空间