/**
 * Using hashmap to reduce time complexity to O(n);
 * the space complexity is O(n)
 */

#include <vector>
#include <map>

using namespace std;

int longestConsecutive(vector<int> &num) {
    map<int, int> cluster;
    int longest = 0;
    
    size_t size = num.size();
    for (int i = 0; i < size; ++i) {
        int n = num[i];
        int &seqs = cluster[n];
        if (seqs != 0) continue;
        
        seqs = 1;
        int lower = cluster[n-1];
        if (lower != 0) {
            seqs = lower + 1;
            // update boundary
            cluster[n-lower] = seqs;
        }
        
        int upper = cluster[n+1];
        if (upper != 0) {
            seqs = seqs + upper;
            // update boundary
            cluster[n+upper] = seqs;
            cluster[n-lower] = seqs;
        }
        
        if (longest < seqs) {
            longest = seqs;
        }
    }
    
    return longest;
}