128 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.

Solution
happy happy, another solution that I can come up with myself.

class Solution {
public:
    int merge(unordered_map<int, int>& record, int n1) {
        // merge n1 and n1+1
        int lbd = n1 + record[n1];
        int ubd = n1+1 + record[n1+1];
        record.erase(record.find(n1));
        record.erase(record.find(n1+1));
        record[lbd] = ubd - lbd;
        record[ubd] = lbd - ubd;
        return (ubd-lbd)+1;
    }
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> record;
        unordered_set<int> tmp;
        int n = nums.size();
        int maxlen = 0;
        for ( int i = 0; i <= n-1; i++) {
            int x = nums[i];
            if ( tmp.find(x) != tmp.end() ) continue;
            tmp.insert(x);
            record[x] = 0;
            maxlen = max(maxlen, 1);
            // nothing to merge
            if ( record.find(x-1) == record.end() and record.find(x+1) == record.end() ) continue;
            // x-1 is in the map, it must be a upper bound
            if ( record.find(x-1) != record.end() and record[x-1] <= 0 ) {
                maxlen = max(maxlen, merge(record, x-1));
            } 
            if ( record.find(x+1) != record.end() and record[x+1] >= 0 ) {
                maxlen = max(maxlen, merge(record, x));
            }
        }
        return maxlen;
    }
};

Notes
Use a hashtable record to record the consecutive sequence.

• record[i] == 0: no neighboring element found;
• record[i] > 0: there exists consecutive sequence from i to i + record[i].
• record[i] < 0: there exists consecutive sequence from i + record[i] to i.

When adding an x, first make sure that x has not been treated yet. (I use an additional set for this, don't know whether there is better way.) Then set record[x] to 0.

• Look for its left neighber x - 1and make sure it's an upper bound. Then merge theses two.
• Look for its right neighber x + 1 and make sure it's a lower bound. Then merge these two.
• The "merge" step includes:
  • find the new upper bound and lower bound;
  • remove the "inside" records;
  • update record[ubd] and record[lbd];
  • return the new consecutive sequence length (ubd-lbd+1).