LeetCode: First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

---

The trick point for this problem is that the index of the array can be utilized as a ordered hash table. While iterating the array, if we find one positive integer that is not in the position of value-1, swap it to that spot. After swapping, we can find the first index where A[index] != index+1. Then it will be the first missing positive.

C++ Code:

/*
 * func: first_missing_positive
 * goal: find the first missing positive integer in the array
 * @param A[]: input array A
 * @param n: the size of the array
 * return: the first missing positive value
 */
/*
 * Put value within range 1 to len(A) to A[index-1]. Then find the 
 * first one that doesn't match.
 * complexity: time O(n), space O(1)
 */
int first_missing_positive(int A[], int n){
    assert(n > 0);
    int index = 0;
    while(index < n){
        if(A[index] > 0 && A[index] <= n && A[A[index]-1] != A[index]){
            std::swap(A[A[index]-1], A[index]);
        }else{
            index += 1;
        }
    }
    
    index = 0;
    while(index < n && A[index] == index + 1){
        ++index;
    }
    
    return index+1;
}

Python Code:

# func: find the first missing positive values in the array
# @param A: input list A
# @return: an integer
# complexity: time O(n), space O(1)
def find_missing_positive(A):
    index = 0
    while index < len(A):
        #If the current value is in the range but not in the right spot
        #Swap it to its spot
        if 0 < A[index] <= len(A) and A[A[index]-1] != A[index]:
            tmp = A[A[index]-1]
            A[A[index]-1] = A[index]
            A[index] = tmp
        else:
            index += 1

    index = 0
    while index < len(A) and A[index] == index+1:
        index += 1

    return index + 1