O(NlogN) soln (Only for concept clarity)


#1
int Solution::firstMissingPositive(vector<int> &A) {

    int N = A.size(), i = 0, negFlag = 0, res = 0;
    sort(A.begin(), A.end());
    if(A[0] > 0 && A[0]!=1) return 1;
    for(i = 0; i<N; i++){
        if(A[i]<0) {
            negFlag++;
            if(A[i+1] > 0 && A[i+1]!=1) return 1;
        }
        else if(A[i]+1 != A[i+1]){
                res = A[i]+1;
                break;
        }
    }
    if(negFlag == N) return 1;
    else return res;
}