First Missing Positive

HardArrays · Cyclic Sort (Index as Hash)🧩 Array Manipulation LeetCode #41 ↗Updated Oct 30, 2026

Problem

Given an unsorted integer array nums, find the smallest positive integer that does not appear in it. The required solution runs in O(n) time using O(1) auxiliary space.

Input[1,2,0]Output3

Input[3,4,-1,1]Output2

Input[7,8,9,11,12]Output1

1 ≤ n ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹-1 · must be O(n) time, O(1) extra space

Try it yourself

Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is always in [1, n+1] (n slots can hold at most 1..n). So only values 1..n matter, and the array itself can act as the hash set: put value v at index v-1.

PatternArray Manipulation

Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.

Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.

Open the Array Manipulation guide →

Approaches

Brute ForceCheck 1, 2, 3, … by Scanning

Time O(n²)Space O(1)

Try candidates i = 1..n+1 in order; for each, scan the whole array. The first candidate not found is the answer — at most n+1 candidates are needed.

Java

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 1; i <= n + 1; i++) {
        boolean found = false;
        for (int num : nums) {
            if (num == i) { found = true; break; }
        }
        if (!found) return i;
    }
    return -1; // unreachable
}

Constant space, but quadratic time.

BetterHash Set Lookup

Time O(n)Space O(n)

Load every value into a HashSet for O(1) membership tests, then walk 1, 2, …, n+1 and return the first one missing.

Java

public int firstMissingPositive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    for (int i = 1; i <= nums.length + 1; i++) {
        if (!set.contains(i)) return i;
    }
    return -1; // unreachable
}

Linear time, but O(n) extra memory violates the constraint.

OptimalCyclic Sort (In-Place Placement)

Time O(n)Space O(1)

While nums[i] is in [1, n] and not already at its home index nums[i]-1, swap it home. Every swap settles one value permanently, so there are ≤ n swaps in total. Then the first index with nums[i] ≠ i+1 gives the answer.

Java

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        // the duplicate check stops infinite swaps of equal values
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            int home = nums[i] - 1;
            int temp = nums[home];
            nums[home] = nums[i];
            nums[i] = temp;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

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

i i changed

i=0
-1
i
4

3

1

3 → idx 2; -1 stops
i=1
-1

1
i
3

4

4 → idx 3
i=1
1

-1
i
3

4

1 → idx 0; -1 stops
i=2,3
1

-1

3

4
i
already home
scan
1

-1
i
3

4

idx1 ≠ 2 → 2 ✔

Linear time, in-place — meets both constraints (mutates the input).

Pro tip

Alternative O(1) trick: mark presence of v by making nums[v-1] negative (after replacing non-positives with n+1).

At a glance

Level	Approach	Time	Space
Brute Force	Check 1, 2, 3, … by Scanning	`O(n²)`	`O(1)`
Better	Hash Set Lookup	`O(n)`	`O(n)`
Optimal	Cyclic Sort (In-Place Placement)	`O(n)`	`O(1)`

Common pitfalls

Swap guard nums[i] != i+1 instead of nums[nums[i]-1] != nums[i] — loops forever on duplicates.
Forgetting to return n+1 when 1..n are all present.
Indexing with an out-of-range value — check 1 ≤ v ≤ n before swapping.

Interview tips

State the [1, n+1] bound first — it is what makes O(1) space possible.
Argue the amortised O(n): each swap places one value at its final index.
Ask whether mutating the input is allowed before going in-place.

Pattern

Cyclic sort / index-as-hash → values lie in 1..n and you need O(1) space presence checks.

My notes saved in this browser