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

The brute-force approach

Use a hash set. Add all positive numbers to the set. Then check 1, 2, 3, ... until you find one not in the set.

seen = set(n for n in nums if n > 0)
i = 1
while i in seen:
    i += 1
return i

O(n) time and O(n) space for the hash set. The constraint requires O(1) space.

Spotting the pattern

This is a Cyclic Sort problem. The key question to ask yourself:

If you could place each number 1..n at its "correct" index (1 at index 0, 2 at index 1, ...), how would you find the first missing positive?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.