Description
Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Examples
Input:
nums = [1,2,0]Output:
3Explanation:
1 and 2 are present, so 3 is the first missing positive.
Input:
nums = [3,4,-1,1]Output:
2Explanation:
1 is present but 2 is missing.
Input:
nums = [7,8,9,11,12]Output:
1Explanation:
All numbers are >= 7, so the smallest positive 1 is absent. Check positives 1,2,3... sequentially.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-2³¹ ≤ nums[i] ≤ 2³¹ - 1