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.

At first I thought the problem means we need to find the first missing positive in a sequence of positive integers, turns out it literately means the first missing integer, like, 1, 2, 3, .., i - 1, i + 1, ... n we are missing i.

Google tells me that we should refer to the Counting sort algorithm. Here is a link of a good of counting sort visualization.

The basic idea is sort all positive elements by swapping them so that they are in the order of A[i] = i  + 1. The missing element must be in the current array, so any element that is larger than A.length or <= 0 is not taken into account.

Traverse the array again and return any element that is not in the correct order, i.e., A[i] != i + 1 or A.length + 1 if everything is in order.

public class MissingPositive {
   public int firstMissingPositive(int[] A) {
        if (A == null)
            throw new NullPointerException("Null array!");
        if (A.length == 0)
            return 1;
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) {
                if (A[A[i] - 1] == A[i])
                    break;
                swap(A, i, A[i] - 1);
            }
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1)
                return i + 1;
        }
        //if every element is in place, we are missing the next one!
        return A.length + 1;
    }
    private void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}