Find the Smallest Missing Positive Integer

Given an unsorted array of integers, possibly containing duplicates, negative numbers, and zeros, find the smallest missing positive integer. The challenge is to achieve an algorithm with \(O(n)\) time complexity and constant extra space.

The idea is to place each number \(x\) in its correct position (i.e. index \(x-1\)) if possible. After the in-place reordering, the first position where the number is not \(i+1\) is the result.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output the smallest missing positive integer to standard output (stdout).

3
1 2 0

3