First Missing Positive

Step 1: The answer is between 1 and n + 1

With n numbers, the best case is that they are exactly 1, 2, ..., n, and then the answer is n + 1. Any gap makes the answer smaller. So values below 1 or above n can never matter.

Step 2: Give each useful value its own slot

If every value v in 1..n were at index v - 1, the answer would be the first index i where nums[i] != i + 1.

Step 3: Place values by swapping (cyclic sort)

For each index i, while nums[i] is in 1..n and not already in its slot, swap it into slot nums[i] - 1. The value that comes back is then placed the same way. Stop when the value is out of range or its slot already holds the right value (which also stops endless swaps on duplicates).

Step 4: Why it is still O(n)

Each swap puts one value in its final slot for good, so there are at most n swaps in total, however the loops are nested.

nums = [3, 4, -1, 1].

Index 1 does not hold 2, so the answer is 2.

The check nums[nums[i] - 1] != nums[i] both detects "already placed" and prevents looping on duplicates.

public class FirstMissingPositive {

    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // Put every value v in 1..n at index v - 1 (cyclic sort)
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int target = nums[i] - 1;
                int tmp = nums[target];
                nums[target] = nums[i];
                nums[i] = tmp;                // the value that was there gets placed next
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;                 // the first slot without its value
            }
        }
        return n + 1;                         // 1..n are all present
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[] {1, 2, 0}));           // 3
        System.out.println(firstMissingPositive(new int[] {3, 4, -1, 1}));       // 2
        System.out.println(firstMissingPositive(new int[] {7, 8, 9, 11, 12}));   // 1
    }
}

The original implementation, FirstMissingPositive.java, is on GitHub.

• Time: O(n).
• Space: O(1); the array is rearranged in place.

Marking slots by sign instead of swapping is the trick in Find All Numbers Disappeared in an Array.