First Missing Positive

Set Matrix Zeroes

Next Permutation

Return the smallest positive integer that does not appear in the array.

Given an unsorted integer array `nums`, return the smallest missing positive integer.

The classic optimal solution runs in linear time and uses constant extra space by reusing the input array itself as bookkeeping.

**Input / output**
- Input: `nums: int[]`
- Output: `int`

**Examples**
1. `nums = [1,2,0]` returns `3`.
2. `nums = [3,4,-1,1]` returns `2`.
3. `nums = [7,8,9,11,12]` returns `1`.

**Constraints**
- `1 <= nums.length <= 100000`
- `-2^31 <= nums[i] <= 2^31 - 1`

**Follow-up**
Can you solve it in `O(n)` time and `O(1)` extra space, and explain why values outside the range `1..n` can be ignored?

- The answer must be in the range `1..n+1` for an array of length `n`.
- Negative numbers, zeros, and values larger than `n` cannot directly block the first missing positive.

Understand what actually matters

- Insert every value into a hash set.
- Then scan upward from `1` until you find the first positive missing from the set.
- This is easy to reason about, but it costs `O(n)` extra space.

Start with a set-based brute-force solution

- Value `1` belongs at index `0`, value `2` at index `1`, and so on.
- If we keep swapping each in-range value into its correct slot, the first index that disagrees with this rule reveals the answer.

Place each value where it belongs

- While a value is in the range `1..n` and not already in its correct slot, swap it into position `value - 1`.
- After that placement phase, scan left to right for the first index whose value is wrong.

Use cyclic placement for O(1) extra space

Trace `nums = [3,4,-1,1]`.

| step | array | explanation |
|---|---|---|
| start | `[3,4,-1,1]` | `3` belongs at index `2` |
| swap | `[-1,4,3,1]` | put `3` into its slot |
| skip | `[-1,4,3,1]` | `-1` is out of range, so move on |
| swap | `[-1,1,3,4]` | `4` belongs at index `3` |
| swap | `[1,-1,3,4]` | then `1` belongs at index `0` |
| scan | `[1,-1,3,4]` | index `1` should contain `2`, so the answer is `2` |

Dry run / placement trace

- Forgetting to keep swapping until the current slot is either invalid or correct.
- Accessing `nums[correct]` before checking that the value is in the range `1..n`.
- Using a clone in a context where the interviewer asked specifically for true `O(1)` extra space.
- Follow-up: can you solve the same problem with sign marking after first normalizing out-of-range values?

Common mistakes and follow-ups

- Arrays containing only negatives should return `1`.
- `[1,2,3]` should return `4`.
- Duplicates like `[1,1]` still return `2`.
- A single `[1]` should return `2`, while a single `[2]` should return `1`.

Edge cases to test mentally

Cyclic placement visits each index a constant number of times, so the optimal approach runs in `O(n)` time with `O(1)` extra space beyond the returned integer.