Sharing my O(1) space solution with explanation


  • 2
    Z
    int firstMissingPositive(int A[], int n) {
        if(n == 0){
            return 1;
        }
        for(int i = 0; i < n; i++){
            if(A[i] > 0 && A[i] - 1 < n && A[i] != A[A[i] - 1]){
                swap(A[i], A[A[i] - 1]);
                i--;
            }
        }
        int minPos = 1;
        for(int i = 0; i < n; i++){
            if(A[i] == minPos){
                minPos++;
            }
        }
        return minPos;
    }
    

    Actually, this problem has only slight differences from Bucket Sort.

    In the first For loop, I do a bucket sort by swapping A[i] and A[A[i] - 1]. Ignore all elements smaller than 0 and larger than n. Also, ignore those elements which are already in the correct position.

    In the second For loop, just to find which positive number is the first missing one, which is trivial.


  • 0
    C

    beautiful solution! Thank you @zxyperfect!

    A little improvement in the second 'for'
    for (i = 0; i < n; i++)
    if (A[i] != i + 1) break;
    return i + 1;


  • 0
    Z

    Thanks for your advice. Your code can make it more efficient :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.