LeetCode - First Missing Positive | Darren's Blog

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.

In other word, “all the numbers are in their correct positions”. What are correct positions? For any i, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions. We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.

public int firstMissingPositive(int[] A) {

        if (A == null || A.length == 0)

            return 1;

        int n = A.length;

        // Put A[i] (>0) at index A[i]-1

        for (int i = 0; i < n; i++) {

            if (A[i] <= n && A[i] > 0 && A[A[i]-1] != A[i]) {

                // Swap A[i] and A[A[i]-1]; note the sequence

                int temp = A[A[i]-1];

                A[A[i]-1] = A[i];

                A[i] = temp;

                // Process A[i] in the next round

                i--;

            }

        }

        // Check the first occurrence of A[i] != i+1

        // If exists, i+1 is the first missing positive; otherwise, the numbers

        // are the first n positve numbers, the first missing one is n+1

        for (int i = 0; i < n; i++) {

            if (A[i] != i+1)

                return i+1;

        }

        return n+1;

    }

Also refer to http://tianrunhe.wordpress.com/2012/07/15/finding-the-1st-missing-positive-int-in-an-array-first-missing-positive/
http://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
Read full article from LeetCode - First Missing Positive | Darren's Blog