visual walkthrough
First Missing Positive
The hardest classic in-place trick (cyclic placement); asked at Google and Amazon.
The idea
With n numbers, the smallest missing positive is at most n + 1. So you only care about values 1…n, and you can park each one in the slot with its own number (value v in slot v − 1).
After shuffling them home, the first slot that doesn't hold its number tells you the answer.
Complexity
| approach | time | space |
|---|---|---|
| Hash set | O(n) | O(n) |
| Swap into place | O(n) | O(1) |