First Missing Integer

• binary search solution
• Time : $O(nlogn)$
• Space : $O(1)$

int Solution::firstMissingPositive(vector<int> &A) {
    sort(begin(A), end(A));
    auto it = upper_bound(begin(A), end(A),0);
    int res = 1;
    while(it != end(A) and *it == res) {
        res++;
        it++;
    }
    return res;
}

• two pointer way solution
• Time : $O(n)$
• Space : $O(n)$

int Solution::firstMissingPositive(vector<int> &A) {
    int res = 1;
    unordered_set<int> us;
    for(auto& a : A) {
        if(a <= 0) continue;
        us.insert(a);
        while(us.count(res)) {
            us.erase(res);
            res++;
        }
    }
    return res;
}