First Missing Positive

Hard

Given an unsorted array nums, return the smallest missing positive integer. Aim for O(n) time and O(1) extra space (use the array itself as a hash).

Example 1

Input:  nums = [1,2,0]
Output: 3

Example 2

Input:  nums = [3,4,-1,1]
Output: 2

Example 3

Input:  nums = [7,8,9,11,12]
Output: 1

Constraints

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1