use the array itself as a hash table. for each number, place it at index (number - 1) if it's in valid range [1, n]. then scan to find first index where nums[i] != i + 1.
the key insight is that for an array of length n, the answer must be in [1, n+1]. by placing numbers at their correct positions, we can identify the missing one in a second pass.
algorithm
- place each number at index (num - 1) if 1 ≤ num ≤ n
- swap to place numbers correctly, handle duplicates
- scan array to find first missing positive
complexity
O(n) time: each element visited at most twice. O(1) space excluding input array.