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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution