Longest Consecutive Sequence

[Question]

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.

[Analysis]
Each element is a consecutive sequence of length 1. Suppose element A, it can be represented as a sequence [A, A+1). If A+1 is in the array, the sequence that starts from A can be represented as [A, A+2). Repeat the finding process, using a hash table which maps A (the starting value) to the ending value (exclusive) of the sequence.

It is equivalent to use mapping between A and "length of consecutive sequence", as shown in 2nd solution code.

[Solution]
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()<2) return num.size();
     
        int max_len = 1;
        unordered_map<int,int> map;    
        for (auto a: num)
            map[a] = a+1;

        for(auto kv: map) {
            int a = kv.first;
            int next = map[a];
            while (map.find(next)!=map.end()) {
                map[a] = map[next];
                map.erase(next);
                next = map[a];
            }
            max_len = max(map[a]-a, max_len);
        }

        return max_len;
    }
};

//Solution 2nd
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.empty()) return 0;
        int max_len = 1;
   
        unordered_map<int,int> map;  
        for (auto& a: num) map[a] = 1;

        for(auto& kv: map) {
            int a = kv.first;
            int next=a+map[a];
            while (map.count(next)) {
                map[a] += map[next];
                map.erase(next);
                next=a+map[a];
            }
            max_len = max(max_len, map[a]);
        }

        return max_len;
    }
};