First Missing Positive

Problem

Given an unsorted integer array nums, return the smallest positive integer (1, 2, 3, ...) that does not appear in it. Aim for linear time and constant extra space; you may rearrange the input array.

• The array is non-empty and has at most 150,000 elements.
• Values are arbitrary signed 32-bit integers, so most of them may be negative, zero, or far larger than the array length.

Examples

• nums = [4, 1, 2, 0] → 3. 1 and 2 are present; 3 is the first gap.
• nums = [5, -3, 1, 6, 3] → 2. 1 is present, 2 is not; the negative and the large values are irrelevant.
• nums = [20, 30, 40] → 1. No small positives at all, so the answer is 1.

Hints

1. The answer is always between 1 and n + 1 inclusive, where n is the array length. Why?
2. That bound means only values in [1, n] matter; everything else can be ignored.
3. Put each value v in [1, n] at index v - 1 by swapping. Afterwards, the first index i where nums[i] != i + 1 gives the answer i + 1.