First Missing Positive
HardP2Coding
Given an unsorted integer array nums, return the smallest positive integer (1, 2, 3, ...) that is not in the array.
Your solution must run in O(n) time and use O(1) auxiliary space (you may reorder the input).
Example 1
- Input
- nums = [1,2,0]
- Output
- 3
- Why
- 1 and 2 are present, 3 is not.
Example 2
- Input
- nums = [3,4,-1,1]
- Output
- 2
- Why
- The 3 and 4 are present but 2 is missing.
Example 3
- Input
- nums = [7,8,9,11,12]
- Output
- 1
- Why
- The array has no 1.
Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.