First Missing Positive

First Missing Positive is a classic "looks impossible, then clicks" problem. The twist is the constraint: do it in O(n) time and O(1) extra space. That rules out sorting and rules out a hash set — so we make the array hash itself.

The slow way first

The easy idea: drop everything into a hash set, then check 1, 2, 3, … until one is missing. That is O(n) time — but it uses O(n) extra space, which the problem forbids.

The question to ask: with n slots in the array, how big can the answer even be? If all of 1..n are present, the answer is n + 1. If something is missing, the answer is somewhere in 1..n. So the answer always lives in the range 1..n+1 — and the array already has n slots to record which of 1..n showed up.

The idea: put each value in its home slot

Give value v a home: slot v - 1. So 1 lives at index 0, 2 at index 1, and so on. Walk the array and, whenever nums[i] is in range 1..n and not already home, swap it to where it belongs. Repeat at the same i until the current value is out of range or already placed. Ignore zeros, negatives, and anything bigger than n — they have no home.

After this pass, every value v in 1..n that exists sits at index v - 1. Now one scan finds the gap: the first index i where nums[i] != i + 1 means i + 1 is missing.

The key insight: the swaps are O(n) total, because each swap puts at least one value permanently into its correct home, and a value never has to be placed twice.

Walk through it

Step through the animation with nums = [3, 4, -1, 1]. Watch values slide into their home slots: 3 goes to slot 2, 4 to slot 3, 1 to slot 0. The junk value -1 has no home, so it sits wherever it lands. After placement the array is [1, -1, 3, 4]. Then pointer i scans: slot 0 holds 1 (good), slot 1 should hold 2 but holds -1 — so the answer is 2.

Pseudocode

n = length of nums
for i from 0 to n-1:
    while nums[i] is in 1..n and nums[i] is not already in its home slot:
        swap nums[i] with nums[nums[i] - 1]   # send it home
for i from 0 to n-1:
    if nums[i] != i + 1:
        return i + 1                           # first gap found
return n + 1                                   # 1..n all present

The Python solution

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

• n is the array length, so the answer is somewhere in 1..n+1.
• The while keeps swapping the value at i until it is out of range or already home — nums[nums[i] - 1] != nums[i] is the "not yet home" test.
• j = nums[i] - 1 is the home slot of the current value; the swap sends it there in O(1).
• The second loop finds the first index whose value is not i + 1; that i + 1 is the missing positive.
• If every slot matches, all of 1..n are present, so we return n + 1.

Complexity

The swaps look like a nested loop, but each successful swap moves one value into its final home and it never moves again — so the total work across both loops is O(n) with only O(1) extra space.

When this pattern shows up

Practice