Find the Smallest Missing Positive Integer

You are given an array of N integers. Your task is to find the smallest positive integer (greater than 0) that does not appear in the array.

For example, if the input array is [3, 4, -1, 1], the smallest missing positive integer is 2. This problem requires an efficient in-place algorithm with a linear time complexity, and the solution should run in O(n) time.

The algorithm works by first replacing all numbers that are not in the range \(1 \ldots N\) with a placeholder value of \(N+1\). Then, it uses the array indices to mark the presence of numbers by making the element at the corresponding index negative. Finally, the first index having a positive number indicates that \(index + 1\) is missing. If all numbers from \(1\) to \(N\) are present, then the answer is \(N+1\).

Input Format: See the input description below.

Output Format: See the output description below.

inputFormat

The first line contains an integer N representing the number of elements in the array. The second line contains N space-separated integers.

outputFormat

Output a single integer representing the smallest missing positive integer.

4
3 4 -1 1

2