Proper O(n) Solution


#1
const int inf = 1e9+7;
int Solution::firstMissingPositive(vector<int> &arr) {
    int n = arr.size();
    for(int i=0;i<n;i++)
    {
       if(arr[i]<1||arr[i]>n)
       arr[i]=inf;
    }
    for(int i=0;i<n;i++)
    {
        if(abs(arr[i])!=inf)
        {
            arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
        }
    }
    /*for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    cout<<endl;*/
   //int prev=1;
    for(int i=0;i<n;i++)
    {
        if(arr[i]>0)
        return i+1;
    }
    return n+1;
}