First Missing Positive
- Array
- In-Place Hashing
Given an unsorted integer array nums, return the smallest positive integer that does not appear in nums.
Your solution should run in O(n) time and use O(1) auxiliary space.
Gap after two present values
- Input
"nums": [2, 5, 1, -3]
- Output
3
Explanation: The values 1 and 2 appear, while 3 does not.
Unordered prefix with a gap
- Input
"nums": [4, 2, 7, 1]
- Output
3
Explanation: The positive prefix contains 1 and 2 but skips 3.
Constraints
- 1 <= nums.length <= 100,000
- -2,147,483,648 <= nums[i] <= 2,147,483,647
Follow-up
Can you use the input array itself as a hash structure by placing each relevant value at its matching index?