Find the Smallest Missing Positive Integer

You are given an unsorted array of integers. Your task is to find the smallest positive integer \(x\) that does not appear in the array.

The algorithm should work in \(O(n)\) time and use constant extra space. The approach commonly involves segregating positive numbers from non-positive ones and then marking the presence of elements in the positive part of the array.

For example, given the array [3, 4, -1, 1], the smallest missing positive integer is 2.

inputFormat

The first line contains a single integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated integers which represent the elements of the array.

outputFormat

Output a single integer: the smallest missing positive integer.

4
3 4 -1 1

2