C++ soln,constant space,O(n)


#1
int Solution::firstMissingPositive(vector<int> &A) {
    int n=A.size();
    for(int i=0;i<n;i++)
    {
        if(A[i]<=0 || A[i]>n+1)
            A[i]=n+2;
    }
    for(int i=0;i<n;i++)
    {
        if(abs(A[i])<=n)
        {
            if(A[abs(A[i])-1]>0)
                A[abs(A[i])-1]*=-1;
        }
    }
    
    for(int i=0;i<n;i++)
    {
        if(A[i]>0)
            return i+1;
    }
    return n+1;
}

#2

I don’t think that your code works for negative values(or zeros) present in array. Correct me if I am wrong.