Find the First Missing Positive Integer

You are given an unsorted integer array. Your task is to find the smallest positive integer that does not appear in the array.

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

Example:

• For input array: [1, 2, 0], the missing integer is 3.
• For input array: [3, 4, -1, 1], the missing integer is 2.
• For input array: [7, 8, 9, 11, 12], the missing integer is 1.

In summary, given an array \(\textbf{nums}\) of length \(n\), find the smallest integer \(\textbf{x}\) such that \(x \ge 1\) and \(x \notin nums\).

inputFormat

The input is provided via stdin as a single line containing space-separated integers representing the elements of the array. The array can be empty.

outputFormat

Output a single integer to stdout which is the first missing positive integer.

1 2 0

3