274. Smallest Missing Positive
Core1000 ms256 MBSolved by 0%
Print the smallest positive integer that does NOT appear among n integers.
Positive means 1 or greater, so the answer is at least 1.
3 4 -1 1 -> 2
1 2 0 -> 3
7 8 9 -> 1
Negatives, zeros and duplicates are all present in the input and none of them can be the answer.
Sort, then walk upwards looking for the first gap. Notice that the answer can
never exceed n + 1, because n values cannot cover more than n distinct
positives.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print one integer, the smallest positive integer not present.
Input4
3 4 -1 1
Output2
Notehas a gap in the middle and a negative to ignore
Input3
7 8 9
Output1
Notecontains no 1 at all, so the answer is the smallest positive
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.