First Missing Positive
The key idea
Among
n numbers, the answer must be one of 1, 2, ..., n, n+1. So the array itself can act as a hash table: put each value v (when 1 <= v <= n) at index v - 1. After that placement, the first index i where nums[i] != i + 1 gives the answer i + 1; if every slot matches, the answer is n + 1.Problem
Given an unsorted integer array nums, return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses constant extra space.
Note that values that are zero or negative, and any duplicates, are simply irrelevant to which small positive number is missing.
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1
Examples
Input: nums = [1,2,0]
Output: 3
Input: nums = [3,4,-1,1]
Output: 2
Input: nums = [7,8,9,11,12]
Output: 1
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM