LeetCode 41 – First Missing Positive

First Missing Positive is Hard because of its constraints, not its question. Finding the smallest absent positive integer is easy with a hash set. Doing it in O(n) time and O(1) extra space forces a genuinely different idea: use the input array itself as the lookup table.

The problem

Given an unsorted array that may contain negatives, duplicates and huge values, return the smallest positive integer that does not appear. O(n) time, constant extra space.

[1, 2, 0]        -> 3
[3, 4, -1, 1]    -> 2
[7, 8, 9, 11, 12] -> 1     nothing small is present
[1, 2, 3]        -> 4      the answer can be one past the end
[]               -> 1

The observation that bounds everything

Start here, because it makes the rest obvious: with n elements, the answer is always somewhere in [1, n + 1].

The array holds n values. In the very best case those are exactly 1, 2, …, n, and then the answer is n + 1. In any other case at least one of 1..n is missing, and the answer is that. There is no arrangement where the answer exceeds n + 1.

So every value outside [1, n] — negatives, zeros, and anything huge — is noise. It cannot be the answer and it carries no information about the answer. That leaves at most n interesting values and exactly n slots to store them in, and slots you already own.

Cyclic sort: the array as its own hash table

Put each value v in [1, n] at index v - 1. Then a single scan finds the first index where nums[i] != i + 1, and i + 1 is the answer.

[3, 4, -1, 1]   n = 4, so only 1..4 matter

3 belongs at index 2  -> swap with -1   [-1, 4, 3, 1]
-1 is noise, move on
4 belongs at index 3  -> swap with 1    [-1, 1, 3, 4]
1 belongs at index 0  -> swap with -1   [1, -1, 3, 4]
-1 is noise, move on

scan: index 0 holds 1 ✓, index 1 holds -1 ✗  ->  answer is 2

The placement uses a while, not an if: after swapping, the value that arrived at i may itself belong elsewhere, so keep going until i holds something that has no home.

Why the nested loop is still O(n)

A while inside a for looks quadratic and is not. Every swap puts at least one value into its final correct index, and a value already in its correct index is never moved again. There are n values, so there are at most n swaps across the entire run. The outer loop contributes another n. Total O(n).

Be ready to say this unprompted — an interviewer looking at that loop will assume O(n²) until you give them the amortised argument.

The condition that prevents an infinite loop

Swapping requires that the destination does not already hold the same value. Without that check, [1, 1] spins forever: the second 1 wants index 0, index 0 already holds 1, the swap is a no-op, and the condition stays true.

Write the guard as nums[nums[i] - 1] != nums[i] — "the slot this value wants does not already contain it" — rather than comparing indices. It handles duplicates and correct placement in one expression.

Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Send every value in [1, n] to index value - 1. Values outside that range
        // are noise and stay wherever they are.
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int target = nums[i] - 1;       // read before the array changes
                int tmp = nums[target];
                nums[target] = nums[i];
                nums[i] = tmp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }

        return n + 1;   // the array was exactly 1..n
    }
}

Compute target before the swap. Writing the three-way exchange in terms of nums[nums[i] - 1] throughout reads compactly and is wrong, because nums[i] changes partway through and the second reference lands somewhere else. This is the kind of bug that survives casual review.

Python

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

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

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

        return n + 1

Python's simultaneous assignment evaluates the right-hand side first, so nums[target], nums[i] = nums[i], nums[target] is safe — but only because target was captured beforehand. Inline the expression and the same trap reappears.

The other O(1) approach

Instead of moving values, mark presence by negating. Overwrite everything outside [1, n] with something harmless like n + 1, then for each value v in range set nums[|v| - 1] negative. The first index still holding a positive is the answer.

Same complexity, three passes instead of two, and it needs care with duplicates so a value is not negated twice back to positive — use -|nums[k]| rather than nums[k] * -1. Cyclic sort is the version worth having in your hands, because it generalises: Find All Numbers Disappeared in an Array (448), Find the Duplicate Number (287) and Missing Number (268) are all the same "value v belongs at index v - 1" trick.

Complexity

O(n) time by the amortised argument above, and O(1) extra space — though it mutates the input, which is the price and should be stated out loud. If the caller needs the array intact, this approach is unavailable and a hash set is the honest answer at O(n) space.

What the interviewer is checking

• That you derive the [1, n + 1] bound before writing anything. Everything follows from it.
• That you use the array as storage, rather than reaching for a set and hoping the constraint was soft.
• That you can prove the nested loop is O(n).
• The duplicate guard — [1, 1] is the test that hangs.
• That the swap captures the target index before mutating.
• [1, 2, 3] returning 4, and an empty array returning 1.
• That you mention the input is destroyed.