First Missing Positive
Hard · hash map
You are given a list of integers nums. It may contain zero, negative numbers and repeated values, in any order.
Return the smallest positive integer (1, 2, 3, ...) that does not appear in nums.
Examples
Example 1
Input: nums = [4, 1, 2, -3, 1]
Output: 3
1 and 2 are present, but 3 is not.
Example 2
Input: nums = [5, 6, 7]
Output: 1
1 is not in the list, and no other positive number can be smaller.
Example 3
Input: nums = [3, 2, 1, 4, 5]
Output: 6
Every number from 1 to 5 is present, so the next one up is missing.
Constraints
- 1 <= len(nums) <= 5000
- -10^9 <= nums[i] <= 10^9