Smallest Missing Positive Integer

You are given an unsorted array of integers nums.

Return the smallest positive integer that does not appear in nums. The positive integers are 1, 2, 3 and so on.

You must write an algorithm that runs in O(n) time and uses constant extra space.

Examples

Example 1

Input: nums = [1, 2, 0]
Output: 3
Explanation: Both 1 and 2 appear, and 3 does not.

Example 2

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: 1 appears but 2 does not, so 2 is the smallest positive integer missing.

Example 3

Input: nums = [7, 8, 9, 11, 12]
Output: 1
Explanation: Nothing in the array equals 1, so the answer is the smallest positive integer of all.