First Missing Positive

HardCyclic SortSeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given an unsorted integer array nums, which may contain negatives, zeros, duplicates and very large values. Return the smallest positive integer (1, 2, 3, ...) that does not appear in nums. Your solution must run in O(n) time and use O(1) extra space, though you may rearrange nums in place.

Examples

nums = [1,2,0] returns 3

1 and 2 are present and 0 isn't positive, so the smallest positive integer that's missing is 3.

nums = [3,4,-1,1] returns 2

1 is present but 2 is not. 3 and 4 don't matter once 2 is missing, and -1 is ignored because it isn't positive.

nums = [7,8,9,11,12] returns 1

1 itself is absent, so the answer is 1 no matter which larger values appear.

Constraints

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

Hints

Hint 1

Only values in 1..n can be the answer, what if each in-range value lived at a predictable spot?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

With n elements the answer lies in 1 to n + 1, so only values 1 to n matter. Swap each such value v into its home, index v - 1, repeating at the same i until the value there is out of range or already has a copy at home; negatives, zeros and values above n stay put. Each swap homes one value for good. Then the first index j with nums[j] != j + 1 gives j + 1; if all match, return n + 1.

Time

O(n)

Space

O(1)

Pitfall

Guard the swap with nums[v - 1] != v, not nums[i] != i + 1. With duplicates like [1,1], the second check keeps swapping a 1 with a 1 forever.

Solutions

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

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        i = 0
        while i < n:
            v = nums[i]
            if 0 < v <= n and nums[v - 1] != v:
                nums[i], nums[v - 1] = nums[v - 1], nums[i]
            else:
                i += 1
        for j in range(n):
            if nums[j] != j + 1:
                return j + 1
        return n + 1