First Missing Positive

Given an unsorted integer array, find the smallest positive integer that is missing from the array. The solution must run in O(n) time using constant extra space.

Examples:

• Input: [3, 4, -1, 1] → Output: 2
• Input: [1, 2, 0] → Output: 3
• Input: [7, 8, 9, 11, 12] → Output: 1

If the array contains all integers from 1 to n, then return \(n+1\).

inputFormat

The input is provided via standard input (stdin) as a single line containing space-separated integers representing the array.

outputFormat

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

3 4 -1 1

2