Array

Longest Consecutive Subsequence

Given an array of integers, find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

int longestConsecutive(const vector<int>& arr){
    std::unordered_set<int> S;
    int n = arr.size();
    for(int i = 0; i < n; ++i){
        S.insert(arr[i]);
    }
    
    for(int i = 0; i < n; ++i){
        if(S.find(arr[i] - 1) == arr.end()){
            int anchor = arr[i];
            while(S.find(anchor) != S.end()){
                anchor++;
            }
            ans = max(ans, anchor - arr[i]);
        }
    }
    return ans;
}