First Missing Positive

hardAmazon-tagged: Mixed28 stepsJava · Python · C++

Find the smallest missing positive integer in O(n) time and O(1) space. The answer is in 1..n+1, so place each value v in 1..n at index v − 1 by swapping. Afterwards, the first index i with nums[i] != i + 1 gives the answer i + 1.

▶ Watch the animated trace

Traced input: nums = [3, 4, -1, 1] → 2. Original problem: neetcode.io/problems/first-missing-positive

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Each swap puts one value in its final place, so at most n swaps.

Key idea

Only values 1..n matter; anything else can be ignored.
Swap nums[i] to its home nums[i] − 1 until the current slot holds a useless or already-placed value.
Check nums[nums[i] − 1] != nums[i] to avoid infinite swaps on duplicates.
If every slot is correct, the answer is n + 1.

Common mistakes

Sorting is O(n log n); a HashSet is O(n) space.
Looping forever on duplicates like [1, 1].

Solution

Java

int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int v = nums[i];
            nums[i] = nums[v - 1];
            nums[v - 1] = v;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Python

def firstMissingPositive(nums: List[int]) -> int:
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            v = nums[i]
            nums[i], nums[v - 1] = nums[v - 1], v
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

C++

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All present Answer is n + 1.	`nums = [1, 2, 3]`	`4`
Large values only Nothing lands in slot 0.	`nums = [7, 8, 9, 11, 12]`	`1`
Duplicates The duplicate check prevents an infinite loop.	`nums = [1, 1]`	`2`
Zero and negatives 1 is missing.	`nums = [0, -5, 2]`	`1`