First Missing Number

leetcode 41.

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.

Solution. I learned the solution from here. The idea is try as much as possible to rearrange array like [1, 2, 3, 4, 5, …].

There are some cases when we pass the iteration.

A[i] < 1 || A[i] > A.length, invalid. For example, we can put [1, 2, 3, 4, 5]. It shows at least we can put 1, at most, we can put 5.

A[i] == i + 1. This is valid situation, so pass.

A[A[i] – 1] == A[i]. Value of position A[i] – 1 is the same as value of A[i], so we don’t swap. One of case is [1, 1].

In all the code is like:

public int firstMissingPositive(int[] A) {
    int i = 0;
    while (i < A.length) {
        // A[i] < 1, A[i] > len, eliminate the invalid value.
        // A[i] == i + 1 is valid, so pass
        // A[i] - 1 and i position has same value. This is the case [1, 1]
        if (A[i] < 1 || A[i] > A.length || A[i] - 1 == i || A[A[i] - 1] == A[i]) {
            i++;
        }
        else {
            swap(A, A[i] - 1, i);
        }
    }
    for (i = 0; i < A.length && A[i] == i + 1; i++);
    return i + 1;
}

private void swap(int[] A, int i, int j){
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

Check my code on github.