Easy solution O(n) time and O(1) space complexity

amazon
Tags: #<Tag:0x00007f1821bb4c80>

#1

First pass sets all values <= 0 and > n to be n+1;
In next pass we go to A[ abs(A[num-1] ) ] and set it to negative if it is not already set. This is simply marking the original array to say that num is present in the array.
Then we simply iterate over the array and find the first position that is positive and return that index plus one.

int Solution::firstMissingPositive(vector<int> &A) {
    int n = A.size();
    for(int i = 0; i< A.size(); i++)
        if(A[i] <= 0 || A[i] > n)    A[i] = n+1;
        
    for(int i = 0; i< A.size(); i++)
    {
        if(abs(A[i]) == n+1)
            continue;
        int num = abs(A[i]);
        if(A[num-1] > 0)     // If negative then already set as visited
            A[num-1] *= -1;
    }
    for(int i = 0; i< A.size(); i++)
        if(A[i] > 0) return i+1;
        
    
    return n+1;
}