Easy O(n) space and time solution using STL


#1

int Solution::firstMissingPositive(vector &A) {
priority_queue<int, vector, greater> q;
for(int i=0;i<A.size();i++){
q.push(A[i]);
}
int temp=1;
for(int i=0;i<A.size();i++){

    if(q.top()<=0){
        q.pop();
    }
    else if(q.top()>temp){
        return temp;
    }
    else if(q.top()==temp){
        temp++;
        q.pop();
    }
}
if(q.empty()){
        return temp;
    }
return temp;

}


#2

This takes O(n + nlogn)