Quick sort kind of partitioning followed by signed approach [More Intuitive O(n) time, O(1) space]


#1
int partition(vector<int> &A) {
    int j = -1;
    int i = 0;
    int n = A.size();
    while(i < n) {
        if(A[i] > 0) {
            swap(A[i], A[j + 1]);
            ++j;
        }
        ++i;
    }
    return j + 1;
    
}
int Solution::firstMissingPositive(vector<int> &A) {
    int n = partition(A);
    for(int i = 0; i < n; ++i) {
        int val = abs(A[i]);
        if(abs(val) - 1 <= n - 1) {
            A[val - 1] = -1 * abs(A[val - 1]);
        }
    }
    for(int i = 0; i < n; ++i) {
        if(A[i] > 0) return i + 1;
    }
    return n + 1;
}