Problem 2.7 · ArraysHard

First Missing Positive

What it teaches: Using the array itself as a hash table: place each value 1..n at index value − 1, then scan for the first gap.

Practise it on judges as “First Missing Positive”.

The problem

Given an unsorted integer array nums, return the smallest positive integer that is not in it. Your algorithm must run in O(n) time and use O(1) extra space.

Example 1

Input: nums = [1, 2, 0]
Output: 3

Example 2

Input: nums = [3, 4, -1, 1]
Output: 2

Example 3

Input: nums = [7, 8, 9, 11, 12]
Output: 1

Constraints

1 ≤ nums.length ≤ 10⁵
−2³¹ ≤ nums[i] ≤ 2³¹ − 1
O(n) time, O(1) extra space

Pattern clues in the wording

→ Answer is always in 1..n + 1 (n slots can hold at most 1..n)
→ O(1) extra space rules out a HashSet
→ Values can act as indexes

These clues point to Index as Hash (Cyclic Sort): When values are in the range 1..n, put each value at its own index (or mark that index) to find missing or duplicate numbers in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

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

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,0]	3
2	nums = [3,4,-1,1]	2
3	nums = [7,8,9,11,12]	1
4	nums = [1,1] Duplicates	2

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Hash set · O(n)2. Optimal: cyclic sort in place · O(n)

Hash set

Time O(n) Space O(n)

Store all values in a set and test 1, 2, 3, ... until one is missing. At most n + 1 tests.

Approach 1

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) seen.add(x);
        int v = 1;
        while (seen.contains(v)) v++;
        return v;
    }
}

Verdict: Correct and fast, but breaks the O(1) space requirement.

Optimal: cyclic sort in place

Time O(n) Space O(1)

Only values 1..n can affect the answer. For each index, while nums[i] is in 1..n and isn't already at its home index nums[i] − 1 (and the home doesn't already hold that value), swap it home. Each swap places one value for good, so there are at most n swaps in total.

Then the first index i where nums[i] != i + 1 gives the answer i + 1. If all match, the answer is n + 1.

▶ Dry run: Placing 1..n at their homesnums = [3, 4, -1, 1]

↑i

-1

Step 1/63 belongs at index 2. Swap with −1.

Approach 2

class Solution {
    public 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 home = nums[i] - 1;
                int tmp = nums[home];
                nums[home] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
        return n + 1;
    }
}

Verdict: Meets both limits. Each swap fixes one value permanently, so the inner loop runs at most n times in total.

Before you submit

Edge cases and common mistakes

Test these inputs

Contains 1..n exactly → n + 1
No 1 at all → 1
Duplicates, e.g. [1, 1]
Very large or negative values

Mistakes people make

Checking nums[i] != i + 1 instead of nums[nums[i] - 1] != nums[i] in the loop condition: with duplicates it swaps forever.
Computing nums[i] - 1 before checking nums[i] >= 1 (index −1).
Using if instead of while: the value swapped in also needs placing.

Interview

Follow-up questions

Why is the inner while loop still O(n) overall?

Can you solve it without swapping, by marking?

Command Palette