O(n) solution by sorting the list using a set (counting sort)


#1
int Solution::longestConsecutive(const vector<int> &A) 
{
    if(A.size() == 0) return 0;
    if(A.size() == 1) return 1;
    int count = 1;
    int maximum = 1;
    
    set<int> nums;
    set<int>::iterator itr;
    
    vector<int> list;
    for(auto& c : A)
        nums.insert(c);

    for(itr = nums.begin(); itr != nums.end(); itr++)
        list.push_back(*itr);
        
    for(int i = 0; i+1 < list.size(); i++)
    {
        if(list[i+1] - list[i] == 1)
            count++;
        else
            count = 1;
        maximum = max(count, maximum);
    }
    
    return maximum;
}