Longest Consecutive Sequence

Three solutions are provided.


//first one
class Solution {
public:
       // Think as cluster merge, a single number is a length=1 cluster.

   // The key factors about a cluster is: lowest, highest, and length.
   // Map lowest and highest to length. To merge two neighbor clusters, only need to update it's new lowest and highest, with new length.
   // For every a[i], checking its neighbor a[i]-1 and a[i]+1 is enough.

int longestConsecutive(vector<int> & a) {
    unordered_map<int, int> amap;
    int amax = 1;
    for (int i=0;i<a.size();i++) {
        if (amap.count(a[i])) continue;
        amap[a[i]]=1;
        if (amap.count(a[i]-1)) {
            amax = max(amax, merge(amap, a[i]-1, a[i]));
        }
        if (amap.count(a[i]+ 1) ){
            amax = max(amax, merge(amap, a[i], a[i]+1));
        }
    }
    return amax;
}

int merge(unordered_map<int, int> &amap, int left, int right) {
    int upper = right + amap[right] - 1;
    int lower = left - amap[left] + 1;
    int len = upper - lower + 1;
    amap[upper]= len;
    amap[lower]= len;
    return len;
}
};

//second, also easy to understand
int longestConsecutive(vector<int> &num) {
    unordered_map<int, int> tail; // Consecutive elements exist between key..value
    for (auto it = num.begin(); it != num.end(); it++) {
        int v = *it;
        if (tail.count(v)) continue; // Skip duplicates
        tail[v] = v;              // First link it to itself
        if (tail.count(v-1)) {    // Numbers before v exists, append itself
            tail[v] = tail[v-1];  // Update tail's head
            tail[tail[v]] = v;    // Update head's tail
        }
        if (tail.count(v+1)) {    // Numbers after v exists, join the 2 links
            int last = tail[v+1]; // Find out the tail
            tail[last] = tail[v]; // Update tail's head
            tail[tail[v]] = last; // Update head's tail
        }
    }
    int maxdiff = 0;
    for (auto it = tail.begin(); it != tail.end(); it++)
        if (it->second - it->first > maxdiff) maxdiff = it->second - it->first ;
    return maxdiff + 1;
}

Basic idea is that tail stores the head or the tail of consecutive numbers. For example, if 1 through 5 have been scanned, then tail[1] = 5 and tail[5] = 1.
Finally, to find out the longest consecutive numbers, simply find the maximum difference between the key and value, and the answer is the max diff plus 1.

//third one by anniekim

int longestConsecutive(vector<int> &num) {
    unordered_set<int> s;
    int res = 0;
    for (int i = 0; i < num.size(); ++i)
        s.insert(num[i]);
    for (int i = 0; i < num.size() && !s.empty(); ++i)
    {
        if (s.find(num[i]) == s.end())
            continue;
        int upper = num[i], lower = num[i];
        while (s.find(upper+1) != s.end())
            s.erase(++upper);
        while (s.find(lower-1) != s.end())
            s.erase(--lower);
        //if (upper != lower)
            s.erase(num[i]);
        res = max(res, upper - lower + 1);
    }
    return res;
}