First Missing Positive

Q: What is the best time complexity for First Missing Positive?

Optimal (place each value at its index) runs in O(n) time and O(1) extra space. Every swap puts one value in its final place, so there are at most n swaps in total, plus one scan.

Q: Which pattern does First Missing Positive use?

It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes, Find All Duplicates in an Array.

Q: Is there a brute force solution for First Missing Positive?

Yes. Brute force takes O(n²) time and O(1) space. Check the candidates 1, 2, 3, … in order.

Q: Which edge cases should I test for First Missing Positive?

All values zero or negative: the answer is 1; The array is exactly 1..n in some order: the answer is n + 1; Duplicates, which can make the in-place swap loop forever if not guarded; Very large values like 2^31 - 1 that are outside 1..n; A single element.

Hard Arrays & Hashing In-place Transformations Original on LeetCode

Reported atMicrosoft Flipkart Walmart Global Tech

First Missing Positive is a hard arrays & hashing problem solved with the in-place transformations pattern. The best approach, optimal (place each value at its index), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an unsorted integer array nums, which may contain negatives, zeros and duplicates. Return the smallest positive integer that does not appear in nums.

Try to do it in linear time while using only a constant amount of extra memory.

Examples

Example 1

Input: nums = [4, -2, 1, 2]
Output: 3
Why: 1 and 2 are present, 3 is not.

Example 2

Input: nums = [5, 6, 9]
Output: 1
Why: 1 itself is missing, so it is the smallest missing positive.

Example 3

Input: nums = [3, 1, 2, 1]
Output: 4
Why: Every value from 1 to 3 is present (1 twice), so the answer is the next one.

Constraints

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
Aim for O(n) time and O(1) extra space.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Better (hash set)	`O(n)`	`O(n)`
Optimal (place each value at its index)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)Up to n + 1 candidates, each needing a full scan of n values.

SpaceO(1)Only loop variables.

Check the candidates 1, 2, 3, … in order. For each candidate, scan the whole array to see whether it is there. The first candidate that is not found is the answer; it is at most n + 1.

For x from 1 to n + 1: scan nums for x.
If x is not found, return x.

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int x = 1; x <= n; x++) {
            boolean found = false;
            for (int v : nums) {
                if (v == x) {
                    found = true;
                    break;
                }
            }
            if (!found) return x;
        }
        return n + 1;
    }
}

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for x in range(1, n + 1):
            found = False
            for v in nums:
                if v == x:
                    found = True
                    break
            if not found:
                return x
        return n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int x = 1; x <= n; x++) {
            bool found = false;
            for (int v : nums) {
                if (v == x) {
                    found = true;
                    break;
                }
            }
            if (!found) return x;
        }
        return n + 1;
    }
};

function firstMissingPositive(nums) {
    const n = nums.length;
    for (let x = 1; x <= n; x++) {
        let found = false;
        for (const v of nums) {
            if (v === x) {
                found = true;
                break;
            }
        }
        if (!found) return x;
    }
    return n + 1;
}

2Better (hash set)

TimeO(n)n inserts and at most n lookups, each O(1) on average.

SpaceO(n)The set can hold all n values.

Put every value into a hash set, then walk x = 1, 2, … until a value is missing from the set. Lookups are O(1), so the walk is linear, at the cost of O(n) extra memory.

Add all values to a set.
For x from 1 to n: if x is not in the set, return x.
Return n + 1.

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

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        seen = set(nums)
        n = len(nums)
        for x in range(1, n + 1):
            if x not in seen:
                return x
        return n + 1

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> seen(nums.begin(), nums.end());
        int n = nums.size();
        for (int x = 1; x <= n; x++) {
            if (!seen.count(x)) return x;
        }
        return n + 1;
    }
};

function firstMissingPositive(nums) {
    const seen = new Set(nums);
    const n = nums.length;
    for (let x = 1; x <= n; x++) {
        if (!seen.has(x)) return x;
    }
    return n + 1;
}

3Optimal (place each value at its index)

TimeO(n)Every swap puts one value in its final place, so there are at most n swaps in total, plus one scan.

SpaceO(1)The array is rearranged in place; only a temporary for swapping.

Use the array as its own lookup table. Each value v with 1 <= v <= n belongs at index v - 1. Swap values into their home positions; skip values outside 1..n, and stop swapping when the home already holds v (this guard handles duplicates). After that pass, the first index i where nums[i] != i + 1 means i + 1 is missing.

For each i: while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i], swap nums[i] with nums[nums[i] - 1].
Scan i from 0 to n - 1: return i + 1 at the first nums[i] != i + 1.
If every position is correct, return n + 1.

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;
    }
}

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

class Solution {
public:
    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;
    }
};

function firstMissingPositive(nums) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            const home = nums[i] - 1;
            const tmp = nums[home];
            nums[home] = nums[i];
            nums[i] = tmp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return n + 1;
}

Edge cases to test

All values zero or negative: the answer is 1
The array is exactly 1..n in some order: the answer is n + 1
Duplicates, which can make the in-place swap loop forever if not guarded
Very large values like 2^31 - 1 that are outside 1..n
A single element

Hints

Hint 1

With n numbers, the answer is always between 1 and n + 1. Why?

Hint 2

So only values in 1..n matter. Could you remember which of them appear using a set, or using the array itself?

Hint 3

Try to 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.

FAQ

What is the best time complexity for First Missing Positive?

Optimal (place each value at its index) runs in O(n) time and O(1) extra space. Every swap puts one value in its final place, so there are at most n swaps in total, plus one scan.

Which pattern does First Missing Positive use?

It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes, Find All Duplicates in an Array.

Is there a brute force solution for First Missing Positive?

Yes. Brute force takes O(n²) time and O(1) space. Check the candidates 1, 2, 3, … in order.

Which edge cases should I test for First Missing Positive?

All values zero or negative: the answer is 1; The array is exactly 1..n in some order: the answer is n + 1; Duplicates, which can make the in-place swap loop forever if not guarded; Very large values like 2^31 - 1 that are outside 1..n; A single element.