Find the smallest positive integer that does not appear in an unsorted array.
Given an unsorted integer array, return the smallest positive integer that is missing from the array.
The solution should be efficient in both time and extra space, and should handle negative numbers, zeros, duplicates, and values larger than the array length.
Input Format
- An integer array
numsof lengthn. - The array may contain any integers, including negatives and zero.
Output Format
- Return the smallest positive integer (
>= 1) that does not appear innums.
Constraints
1 <= n(reasonable interview-sized input)- Values may be negative, zero, or positive
- Aim for time and extra space if possible
Example 1
Input
nums = [1,2,0]
Output
3
Explanation
The positive integers 1 and 2 are present, so the smallest missing positive is 3.
Example 2
Input
nums = [3,4,-1,1]
Output
2
Explanation
1 and 3 are present, but 2 is missing.
Show 1 more example
Example 3
Input
nums = [7,8,9,11,12]
Output
1
Explanation
No positive integer starting from 1 appears in the array.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.