First Missing Positive [Hard] — Cyclic Sort / Index Marking

Problem Statement

Given an unsorted integer array, find the smallest missing positive integer. Must run in O(n) and O(1) extra space.

Input: [1,2,0]     → Output: 3
Input: [3,4,-1,1]  → Output: 2
Input: [7,8,9,11,12] → Output: 1

Intuition

Cyclic Sort: Place each positive integer x (1 ≤ x ≤ n) at index x-1. After sorting, first index where nums[i] != i+1 gives the answer.

Solutions

C++

int firstMissingPositive(vector<int>& nums) {
    int n=nums.size();
    for (int i=0;i<n;i++)
        while (nums[i]>0&&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;
}

Java

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

JavaScript

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

Python

def firstMissingPositive(nums: list[int]) -> int:
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Complexity

Time: O(n) — each swap places one element correctly
Space: O(1)