Smallest positive left out
Reported in interviews at (where)
Given an unsorted list of whole numbers nums (any of them may be negative, zero or repeated), return the smallest positive whole number (1, 2, 3, ...) that does not appear in it.
The real test is doing it in O(n) time with only O(1) extra space: you may rearrange nums itself.
- Input
nums = [7,8,9]- Output
1
1 is not there.
- Input
nums = [1,4,2]- Output
3
1 and 2 are there, 3 is not.
- Input
nums = [2,-1,1,3,3]- Output
4
Negatives and repeats change nothing: 1, 2 and 3 are there.
Limits
1 <= nums.length <= 100000-2^31 <= nums[i] <= 2^31 - 1
Hints
Hint 1
The answer is at most n + 1.
Hint 2
Put each value v from 1 to n at position v - 1 by swapping, then find the first position that holds the wrong value.
Where this was reported
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
