First Missing Positive
Problem
Given an unsorted integer array nums, return the smallest missing positive integer. Your algorithm must run in O(n) time and use O(1) extra space.
Examples
Example 1
Input: nums = [1,2,0]
Output: 3
Explanation: 1 and 2 are present, 3 is the smallest missing positive.
Example 2
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is present, 2 is missing.
Constraints
- •
1 <= nums.length <= 10^5 - •
-2^31 <= nums[i] <= 2^31 - 1
Hints
Hint 1
A hash set of all positive values, then checking 1, 2, 3, ... in order until one is missing, is correct in O(n) time — but again costs O(n) space, disallowed here.
Hint 2
The answer is guaranteed to be in [1, n+1] — so only values in that narrow range are ever relevant, everything else (negatives, zero, values > n) can be ignored.
Hint 3
Cyclic sort: repeatedly swap each in-range value to its 'correct' index (value v belongs at index v-1) — afterward, the first index that doesn't hold its expected value reveals the answer.
Solutions
public int firstMissingPositiveHashSet(int[] nums) {
Set<Integer> present = new HashSet<>();
for (int n : nums) present.add(n);
int i = 1;
while (present.contains(i)) i++;
return i;
}Time: O(n) · Space: O(n) — violates the problem's O(1) space requirement