Skills101
← All coding problems

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: n integers

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).

Loading editor…

Log in to run and submit your code — it's free.