Smallest Missing Positive Integer in Linear Time and Constant Extra Space

You are given an unsorted list of integers `nums`, which may contain negative numbers, zeros, duplicates, and values far larger than the length of the list. Return the smallest positive integer, that is the smallest integer that is at least `1`, that does not appear in `nums`. In the interview, a first solution that ran in linear time but used extra memory proportional to the input was accepted as a starting point, and the interviewer then asked for the same result using only constant extra space. Aim for that tighter target. ### Function Signature ```python def first_missing_positive(nums: list[int]) -> int: ``` ### Rules - Target complexity: `O(n)` time and `O(1)` auxiliary space, where `n = len(nums)`. The list may be rearranged or overwritten in place; its contents after the call do not matter. - Return only the missing value. ### Constraints - `1 <= len(nums) <= 10^5` - `-2147483648 <= nums[i] <= 2147483647` - The answer is a positive integer that fits in a signed 32-bit integer. ### Examples **Example 1** - Input: `nums = [4, -2, 1, 2]` - Output: `3` - Explanation: `1` and `2` are present and `3` is not. **Example 2** - Input: `nums = [5, 6, 100, -3]` - Output: `1` - Explanation: `1` does not appear, so it is the answer, however large the other values are. **Example 3** - Input: `nums = [1, 2, 2, 3]` - Output: `4` - Explanation: `1`, `2` and `3` all appear (`2` twice), so the smallest missing positive integer is `4`.