Best solution - O(n) time and no extra space! no swapping


#1
int Solution::firstMissingPositive(vector<int> &A) {
    bool checkone=false;
    for(int j=0;j<A.size();j++){
        int c = A[j];
        if(c==1){
            checkone = true;
        }
        if(A[j]<=0 || A[j]>A.size()){
            A[j]=1;
        }
    }
    if(checkone == false){
        return 1;
    }
    
    for(int j=0;j<A.size();j++){
        int c = abs(A[j])-1;
        if(A[c]>0){
            A[c]=A[c]*(-1);
        }
            
    }
    int answer=0;
    for(int i=0;i<A.size();i++){
        if(A[i]>0){
            answer = i+1;
            break;
        }
    }
    if(answer==0){
        return A.size()+1;
    }
    return answer;
    
}