We’re preparing your current view and syncing the latest data.
Given an unsorted integer array nums, find the smallest missing positive integer. Your algorithm should run in O(n) time and use constant extra space.
An integer array nums of length n.
Return the smallest positive integer that does not appear in nums.
1 <= nums.length <= 5 * 10^5 -2^31 <= nums[i] <= 2^31 - 1
Example 1
Input
[1,2,0]
Output
3
Explanation
The numbers 1 and 2 are present, so the first missing positive is 3.
Example 2
Input
[3,4,-1,1]
Output
2
Explanation
1 is present, but 2 is missing; hence 2 is the answer.
Example 3
Input
[7,8,9,11,12]
Output
1
Explanation
1 is the smallest missing positive number since none of 1, 2, ... are present.