First Missing Positive

Rearrange the array in place so every useful number points to its own home slot, then read the first empty home.

The memory hook

Every positive x ≤ n belongs in slot x − 1; the first slot that breaks that rule is the answer.

HardIn-place index placementO(n) timeO(1) space

Make the array its own checklist

intuition

The answer cannot be larger than n + 1. That means the only values worth organizing are 1 through n; negatives, zeros, and oversized values can be ignored.

1Name the homesIndex 0 is the home for 1, index 1 is the home for 2, and so on. A value x is useful only when 1 ≤ x ≤ n.

2Swap, don’t markWhile nums[i] has a useful value that is not already in its home, swap it into index nums[i] − 1. The duplicate guard prevents cycling.

3Read the gapAfter placement, scan left to right. The first index i where nums[i] is not i + 1 is the smallest missing positive.

The one sentence to remember: The array becomes a presence table: value x is present exactly when slot x − 1 contains x.

Watch values find their homes

playable trace

Each frame mirrors one swap or one invariant check in the code. Green slots already contain their home value; the final cyan slot marks the first gap.

Playable trace · In-place index placement

Frames are generated from the same logic as the code below.

Presets

Current event

Ready — press Play

First missing positive

array slots

Useful values will be moved to their matching index; duplicates and out-of-range values stay harmless.

unread current home satisfied just moved first gap

0 / 0 speed 650ms

Place, then scan

the solution

Python · In-place index placement

def firstMissingPositive(nums):
    n = len(nums)

    # Put each useful value x into slot x - 1.
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    # The first slot that misses its home value is the answer.
    for i, value in enumerate(nums):
        if value != i + 1:
            return i + 1
    return n + 1

The inner loop may look nested, but every successful swap puts a value into its final home. Across the whole run, there are at most O(n) swaps.

Useful range1 ≤ x ≤ nOnly these values can change whether the answer is one of the first n positives.

Home slothome(x) = x − 1When x reaches index x − 1, the array records that x exists without extra memory.

First gapnums[i] ≠ i + 1The scan stops at the first mismatch; every earlier positive has already been accounted for.

Why does the first mismatch give the smallest answer? The placement loop establishes the invariant that every correctly placed x has nums[x − 1] = x. Therefore, if slots 0 through i − 1 match, positives 1 through i exist; the first mismatch at i proves i + 1 is absent.

TimeO(n)The scan is linear, and each swap settles a value into a home slot, so total work is amortized O(n).

SpaceO(1)The swaps reuse nums; only a constant number of indices and temporaries are allocated.

Two quick mental checks

make it stick

[3, 4, -1, 1]

→ 2

After swaps, 1 sits at slot 0 while slot 1 cannot hold 2. The first gap is 2.

[1, 2, 0]

→ 3

Slots 0 and 1 contain 1 and 2; the next positive, 3, is the first one missing.

What to say out loud

I only care about values from 1 to n. I use each value as an address, swap it into its home slot, and then the first index i without i + 1 is the answer.