Problem statement

Given an unsorted integer array nums, return the smallest positive integer that is not present.

An O(n) time, O(1) extra-space solution exists (index marking).

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 <= 30
• -100 <= nums[i] <= 100

Hints for First Missing Positive

1. Hint 1

   The answer is always between 1 and n+1 inclusive.

2. Hint 2

   Try to place each value v at index v-1, then scan for the first index where nums[i] != i+1.

How to solve First Missing Positive

With n values, the answer must lie in 1 .. n+1 — if every one of 1 .. n is present the answer is n+1, and otherwise it is the smallest one missing. That bound is what makes the problem tractable: only values inside that window matter, and everything else (negatives, zeros, values above n) can be ignored outright.

Approach

1. Mark which of the values 1 .. n actually appear, ignoring anything outside that range.
2. Scan v from 1 upwards.
3. Return the first v whose mark is absent.
4. If all are present, return n + 1.

Why it works

The pigeonhole principle gives the bound: n values cannot cover 1 .. n+1, so a missing positive always exists at or below n+1. Values outside 1 .. n can never be the answer's neighbours in any useful way — they only fill slots that do not exist — so discarding them loses nothing. The O(1)-space version stores the same marks inside the input, either by permuting each value v into position v-1 or by negating the slot it indexes.

Complexity

• Time — O(n)
• Space — O(n), or O(1) marking in place

Pitfalls

• The answer can be n + 1, so the scan must extend one past the array length.
• Filter out non-positive values and anything larger than n before indexing, or you read out of bounds.
• Duplicates are harmless — marking a slot twice changes nothing.
• Sorting first works but costs O(n log n), which the problem's O(n) target rules out.

Reference solution

Python

from typing import List

def firstMissingPositive(nums: List[int]) -> int:
    s = set(nums)
    i = 1
    while i in s:
        i += 1
    return i

Java

public static int firstMissingPositive(int[] nums) {
    int n = nums.length;
    boolean[] seen = new boolean[n + 2];
    for (int x : nums) {
        if (x >= 1 && x <= n) seen[x] = true;
    }
    for (int v = 1; v <= n + 1; v++) {
        if (!seen[v]) return v;
    }
    return n + 1;
}

C++

int firstMissingPositive(vector<int>& nums) {
    int n = (int) nums.size();
    vector<bool> seen(n + 2, false);
    for (int x : nums) {
        if (x >= 1 && x <= n) seen[x] = true;
    }
    for (int v = 1; v <= n + 1; v++) {
        if (!seen[v]) return v;
    }
    return n + 1;
}

JavaScript

var firstMissingPositive = function(nums) {
    const s = new Set(nums);
    let i = 1;
    while (s.has(i)) i++;
    return i;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard