First Missing Positive Integer

Given an unsorted array of integers, the task is to find the smallest missing positive integer. In other words, find the smallest integer \( x \) such that \( x > 0 \) and \( x \) is not present in the array.

The solution should ideally run in \( O(n) \) time complexity and use constant extra space.

inputFormat

The input is read from standard input (stdin). It consists of two lines:

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

outputFormat

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

4
3 4 -1 1

2