Given an unsorted integer array nums, return the smallest positive integer that doesn't appear in it.
The catch: do it in O(n) time using only O(1) extra space.
Examples
Example 1
- Input
- nums = [1, 2, 0]
- Output
- 3
Example 2
- Input
- nums = [3, 4, -1, 1]
- Output
- 2
Example 3
- Input
- nums = [7, 8, 9, 11, 12]
- Output
- 1
- Why
- 1 is already missing.
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1