First Missing Positive
Problem
Given an unsorted integer array, return the smallest positive integer that does not appear in it. The solution must run in O(n) time and use only constant extra space.
Examples
Constraints
- • 1 <= nums.length <= 10^5
- • -2^31 <= nums[i] <= 2^31 - 1
Hints & approach
Hint 1
The answer is always between 1 and n + 1.
Hint 2
Values outside 1..n can be ignored; the rest could each live at a "home" index.
Hint 3
Swap every value v into index v - 1, then look for the first index that does not hold its own value.
Approachtry the hints first
Only values 1..n can affect the answer. Do a cyclic placement: for each index, while nums[i] is in 1..n and nums[nums[i] - 1] != nums[i], swap nums[i] to its home index nums[i] - 1. Each swap puts at least one value in its final place, so the total work is linear. Afterwards, the first index i with nums[i] != i + 1 gives the answer i + 1; if all match, the answer is n + 1.
Time O(n) · Space O(1)