First Missing Positive
You get an integer array nums. It is not sorted. It can contain negative numbers, zeros and repeated numbers.
Return the smallest positive integer (1, 2, 3, ...) that does not appear in nums.
Try to solve it in O(n) time while using only O(1) extra space. Changing nums itself is allowed.
Hint
If the array has n numbers, the answer is at most n + 1. So only the values from 1 to n matter. Can you use the array positions themselves to remember which of those values you have seen?
Examples
Example 1
- Input:
- [4,-2,1,2]
- Output:
- 3
1 and 2 are in the array, but 3 is not.
Example 2
- Input:
- [5,6,7]
- Output:
- 1
1 is not in the array, so the answer is 1.
Example 3
- Input:
- [2,1,3,3]
- Output:
- 4
1, 2 and 3 are all present. The next positive integer, 4, is missing.
Constraints
1 <= nums.length <= 20-30 <= nums[i] <= 40
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.