First Missing Positive

The array is not just input. Under the right invariant, it becomes its own presence map.

The required bounds force that design:

1. The answer is bounded by 1 through n + 1.
2. Every useful value x can be placed at index x - 1.
3. The first index that does not contain its expected value reveals the answer.

The swap is easy. The real work is deriving the range, preventing duplicate-induced no-progress cycles, and proving that the placement phase remains linear.

Bound the answer before touching the array

Let n = len(nums).

The smallest missing positive integer must be in:

[1, n + 1]

If one of 1 through n is missing, the answer is inside that range. If all of them are present, the answer is n + 1. There are only n array positions, so the answer cannot be larger.

That immediately classifies the input:

• Values <= 0 cannot be the answer.
• Values > n cannot be the answer.
• Only values in [1, n] need to be represented during placement.

A hash set would make membership testing straightforward, but it uses O(n) auxiliary space. Sorting avoids the set but costs O(n log n). The required O(n) time and O(1) auxiliary space leave a narrower path:

Use the array's positions to represent presence.

For every relevant value x, give it a home:

x -> index x - 1

So the desired positional relationship is:

index:  0   1   2   ...  n - 1
value:  1   2   3   ...  n

This is often called cyclic sort or index placement. The label is less important than the obligation: a bounded value has a direct destination, so we can use the array as a sparse presence map without allocating another one.

Derive the guarded placement loop

Process each index i. Let the current value be:

x = nums[i]

We can move x only if it is in [1, n]. Its target index is:

target = x - 1

But range checking is not enough. The target may already contain another copy of x.

The complete swap condition is:

1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]

If that condition holds, swap the current value with the value at its home index.

The duplicate check is a progress condition. Consider:

[1, 1]

At index 1, the current value is 1, whose home is index 0. But index 0 already contains 1. Swapping would exchange equal values and leave the array unchanged. Repeating that operation would create an infinite loop.

When the target already contains x, the array has already recorded the only presence fact that x can provide. Stop processing that position.

After a swap, do not advance i immediately. The displaced value has just arrived at index i, and it may have its own home elsewhere. The while loop must inspect the same position again.

Dry run: [3, 4, -1, 1]

Start with:

[3, 4, -1, 1]

At index 0, 3 belongs at index 2:

[3, 4, -1, 1]
    swap indices 0 and 2
[-1, 4,  3, 1]

Index 0 now contains -1, which is outside the useful range. Move to index 1.

At index 1, 4 belongs at index 3:

[-1, 4, 3, 1]
    swap indices 1 and 3
[-1, 1, 3, 4]

The displaced value 1 is now at index 1. Its home is index 0:

[-1, 1, 3, 4]
    swap indices 1 and 0
[ 1,-1, 3, 4]

Index 1 now contains -1, so placement stops.

The resulting state is:

[1, -1, 3, 4]

Values 1, 3, and 4 occupy their home slots. Position 1 does not contain 2, which is the first missing positive.

Prove placement, progress, and the first mismatch

The placement loop maintains this condition at every index it finishes processing:

The current value is invalid, already at its home index, or blocked because an identical value already occupies its home index.

Each successful swap places a valid value x at index x - 1.

That placement is permanent. Once x occupies its home slot, a later value can target that slot only if it is another x. The duplicate guard prevents that later swap. Therefore, every successful swap establishes a home-slot fact that will not be undone.

This proves the O(n) time bound despite the nested while loop:

• The outer loop inspects n positions.
• Each successful swap permanently fills one home slot.
• There are only n home slots.

So the total work is:

O(n) outer inspections + O(n) successful swaps = O(n)

The scan after placement relies on the same invariant. At index i, the expected value is i + 1:

if nums[i] != i + 1:
    return i + 1

Why does a mismatch certify absence rather than merely misplaced data?

For every value x in [1, n], placement has exhausted its only possible home slot, index x - 1. If x existed, it would be there after the placement phase. Therefore, when position i does not contain i + 1, the value i + 1 is absent.

The first mismatch also proves minimality: every earlier position matched, so every smaller positive value is present. The current expected value is the smallest absent one.

If the entire scan matches, every value from 1 through n is present, so the answer is n + 1.

Implement the Python solution

def first_missing_positive(nums: list[int]) -> int:
    n = len(nums)

    for i in range(n):
        while (
            1 <= nums[i] <= n
            and nums[i] != nums[nums[i] - 1]
        ):
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1

Each condition has a specific obligation:

• 1 <= nums[i] <= n prevents invalid indexing and ignores irrelevant values.
• nums[i] - 1 converts a value into its home index.
• nums[i] != nums[nums[i] - 1] prevents duplicate-induced no-progress cycles.
• The while loop keeps processing displaced values at the current index.
• The final scan converts the first positional mismatch into the missing value.
• n + 1 handles the case where every valid position is correct.

The function mutates nums, but uses only a fixed number of local variables. Its auxiliary space is therefore O(1).

The interview explanation in five steps

Under interview pressure, explain the derivation in this order:

1. Bound: The answer is in [1, n + 1], so values outside [1, n] are irrelevant.
2. Home slot: Value x belongs at index x - 1.
3. Guarded placement: Swap while the current value is valid and its home does not already contain that value.
4. Scan: The first index i with nums[i] != i + 1 gives the answer i + 1.
5. Proof: Each successful swap permanently fills a home slot, so placement and scanning are both linear.

That explanation is short enough to rehearse and precise enough to defend.

Audit the failure boundaries

Each edge case tests a different part of the invariant.

Input pattern	What it tests	Result
[2, 3, 4]	Missing 1	1
[1, 2, 3]	Every valid value present	4
[-3, 0, -1]	Non-positive values	1
[7, 8, 9]	Values larger than n	1
[1, 1]	Duplicate guard	2
[2, 3, 1]	Displaced cycle	4

For [2, 3, 1], placement follows the destinations:

2 -> index 1
3 -> index 2
1 -> index 0

The while loop drains the cycle until every value reaches its home.

The most common implementation failures are mechanical but revealing:

• Using x as an index: The correct target is x - 1.
• Forgetting the range check: Negative or very large values must never be used for indexing.
• Omitting the duplicate guard: Equal values can be swapped forever.
• Advancing after a swap: The displaced value at the current index may still need placement.
• Returning the wrong scan value: Index i represents the candidate i + 1.
• Stopping after n: If all positions match, the answer is n + 1.

Keep these two conversions visible while coding:

value x  -> index x - 1
index i  -> expected value i + 1

Most off-by-one bugs in this problem come from switching those directions halfway through the implementation.

Complexity and decision boundary

The final costs are:

Time:  O(n)
Space: O(1) auxiliary space

The method works because the relevant values form a bounded domain with a direct address, and the input array may be rearranged in place.

That is the decision boundary for this pattern. If values have no safe mapping to array positions, or if the array cannot be mutated, index placement is no longer the right tool. Use the technique because the value domain earns it—not because a tutorial labels the problem “cyclic sort.”

The transferable rule

When an array problem asks about missing or present values, first ask:

Is the useful value range bounded by the array length, and does each useful value have a direct home index?

If yes, derive the solution from five obligations:

1. Bound the relevant values.
2. Map each value to its home index.
3. Guard against invalid values and duplicate no-progress states.
4. Prove that placement creates permanent facts.
5. Scan for the first broken expectation.

Then test a duplicate-heavy input before trusting the code. A correct constant-space array algorithm should keep making progress, even when the data contains noise, duplicates, and displaced cycles.