First Missing Positive

## Problem Given an unsorted integer array `nums`, return the **smallest missing positive integer**. You must implement an algorithm that runs in **O(n) time** and uses **O(1) auxiliary space**. ## Examples **Example 1:** ``` Input: nums = [1,2,0] Output: 3 Explanation: The numbers in the range [1,2] are all in the array. The smallest missing positive is 3. ``` **Example 2:** ``` Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing. ``` **Example 3:** ``` Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest missing positive is 1. ``` ## Approach Hints Use the array itself as a hash map. For each number in range [1, n], place it at index `num - 1` using swaps. After rearranging, the first index `i` where `nums[i] != i + 1` gives the answer `i + 1`.