Problem
Given an unsorted integer array, return the smallest positive integer (>= 1) that does not appear in it, in O(n) time using O(1) auxiliary space.
Input / Output
- Input:
nums, an array of n integers with arbitrary values.
- Output: a single integer — the smallest missing positive.
Constraints
- O(n) time and O(1) extra space, so a hash set is disallowed and sorting at O(n log n) is too slow.
- The array may contain negatives, zeros, duplicates, and values larger than n.
- Mutating the input array is permitted.
Example
- [3,4,-1,1] → 2
- [1,2,0] → 3
- [7,8,9,11,12] → 1 (no value falls in the useful range, so the answer is 1)
- [1,2,3] → 4 (everything present, so the answer is n+1)
- [1,1] → 2 (duplicates must not cause an infinite swap loop)