First Missing Positive
hardArrays & Prefix Sums+40 XPTime limit 2s
Find the smallest positive integer (1, 2, 3, …) that does not appear in the array. The array is unsorted and may contain zeros, negatives and repeats.
Input:
- line 1:
n - line 2:
nintegers
Output: the smallest missing positive integer.
Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹.
Challenge: a hash set or sorting is easy. Do it in O(n) time and O(1) extra space.
Think about it: the answer is always between 1 and n + 1. Use the array as its own hash table: keep swapping each value v in 1..n into position v − 1 until every cell holds the right value or a useless one. Then the first position i with a[i] ≠ i + 1 gives the answer.
Sample input 1
4 3 4 -1 1
Sample output 1
2
Sample input 2
3 1 2 0
Sample output 2
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).