41. First Missing Positive
You are handed an unsorted integer array nums — the values can be negative, zero, duplicated, or astronomically large. Return the smallest positive integer that is absent from the array.
So if 1 is missing the answer is 1; if 1, 2, 3 are all present but 4 is not, the answer is 4 — regardless of what garbage values sit around them.
What makes this Hard is the target bound: solve it in O(n) time using O(1) extra space (you may rearrange nums itself).
Example 1:
Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: 1 appears, but 2 does not, so 2 is the smallest missing positive.
Example 2:
Input: nums = [1, 2, 0]
Output: 3
Explanation: 1 and 2 are both present, so the hunt stops at 3.
Example 3:
Input: nums = [7, 8, 9, 11, 12]
Output: 1
Explanation: Nothing in the array equals 1, and 1 is the smallest positive integer of all.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Hints:
For an array of length n, the answer can only be one of 1, 2, …, n+1. Values that are negative, zero, or larger than n can never change it — they are noise.
With extra memory this is easy: drop everything into a hash set, then probe k = 1, 2, 3, … until a probe misses.
For O(1) space, use the array as its own hash table: value v 'wants' to live at index v−1. Swap each in-range value into its home cell (a cyclic sort), then the first index i where nums[i] != i+1 exposes the answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 4, -1, 1]
Expected output: 2