105. Smallest Absent Positive
A warehouse stamps each crate with a positive serial number, starting at 1. The array nums holds the serial numbers read by a scanner during one shift, but the scanner is unreliable: it may output zeros, negative values, very large values and repeated readings.
Return the smallest positive integer that does not appear in nums. The readings are not sorted, and you are allowed to reorder or overwrite nums while you work. Aim for linear total work and only a constant amount of extra memory, so building a separate hash set of every reading is not the intended approach.
Example 1
- Input:
- nums = [4,-2,1,3,2,7]
- Output:
- 5
- Explanation:
Serials 1, 2, 3 and 4 are all present, but 5 is missing.
Example 2
- Input:
- nums = [9,8,7]
- Output:
- 1
- Explanation:
Serial 1 never appears, so it is the smallest absent positive.
Example 3
- Input:
- nums = [2,2,1,0,3,4,5]
- Output:
- 6
- Explanation:
The values 1 through 5 are present (duplicates and the zero are ignored), so the answer is 6.
Constraints
1 ≤ nums.length ≤ 105
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)