431. First Missing Positive
HardArrayCyclic Sort
Print the smallest positive integer that does not appear in the array. Aim for O(n) time and O(1) extra space.
Input format
Line 1: n Line 2: n integers
Output format
The smallest missing positive.
Example 1
Input
3 1 2 0
Output
3
Example 2
Input
4 3 4 -1 1
Output
2
Constraints
1 ≤ n ≤ 10⁵
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…