LeetCode #41 — Hard

First Missing
Positive

A complete visual walkthrough of the cyclic sort trick — using the array itself as a hash map in O(n) time and O(1) space.

Solve on LeetCode

The Problem

Problem Statement

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

Step 01

Brute Force Approaches

There are two common brute-force approaches that each violate one of the constraints.

Approach 1: Sort First

Sort the array, then scan for the first missing positive. Time: O(n log n) — violates the O(n) requirement.

Approach 2: HashSet

Insert all values into a HashSet, then check 1, 2, 3, ... until one is missing. Time: O(n) but Space: O(n) — violates the O(1) space requirement.

The problem demands O(n) time AND O(1) extra space. That means we cannot sort and cannot use extra data structures. We need to use the input array itself as our storage.

💡

Key observation: For an array of length n, the answer must be in the range [1, n+1]. Why? In the best case, the array contains exactly {1, 2, ..., n}, so the answer is n+1. Otherwise, some number in [1, n] is missing.

Step 02

The Core Insight — Array as Hash Map

Since the answer is in [1, n+1], we only care about values 1 through n. The brilliant idea: place each number at its "correct" index. Number 1 goes to index 0, number 2 goes to index 1, ..., number k goes to index k-1.

The Mapping: nums[i] should equal i + 1

After rearranging, a "perfect" array looks like this:

index

value

After cyclic sort, we scan left to right. The first index where nums[i] != i + 1 gives us the answer: i + 1.

The Swap Condition

We swap nums[i] to its correct position when ALL of these hold:

nums[i] > 0

Only positive numbers matter

nums[i] <= n

Must fit within the array bounds

nums[nums[i] - 1] != nums[i]

nums

-1

i=0 i=1 i=2 i=3

Scan: nums[0]=1 (ok), nums[1]=-1 != 2 → Answer is 2

Step 04

Edge Cases

All positive consecutive: [1, 2, 3]

Every slot is correct. Answer = n + 1 = 4.

All negative: [-3, -2, -1]

No swaps happen. First scan: nums[0] != 1. Answer = 1.

Contains duplicates: [1, 1]

nums[0]=1 correct. nums[1]=1 but should be 2. The swap condition nums[nums[i]-1] != nums[i] prevents infinite swapping of equal values. Answer = 2.

Single element: [1]

Already correct. Answer = 2.

Large values: [100, 200, 300]

All values exceed n=3, so no swaps. Answer = 1.

Step 05

Full Annotated Code

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Phase 1: Cyclic sort — place each number at its "home" index
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0              // positive
                && nums[i] <= n              // within bounds
                && nums[nums[i] - 1] != nums[i]) {  // not already placed

                // Swap nums[i] to its correct position nums[i]-1
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }

        // Phase 2: Scan for first index where nums[i] != i+1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }

        // All slots [1..n] are filled correctly
        return n + 1;
    }
}

func firstMissingPositive(nums []int) int {
    n := len(nums)

    // Phase 1: Cyclic sort — place each number at its "home" index
    for i := 0; i < n; i++ {
        for nums[i] > 0 &&           // positive
            nums[i] <= n &&           // within bounds
            nums[nums[i]-1] != nums[i] {  // not already placed

            // Swap nums[i] to its correct position nums[i]-1
            dest := nums[i] - 1
            nums[i], nums[dest] = nums[dest], nums[i]
        }
    }

    // Phase 2: Scan for first index where nums[i] != i+1
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }

    // All slots [1..n] are filled correctly
    return n + 1
}

def first_missing_positive(nums: list[int]) -> int:
    n = len(nums)

    # Phase 1: Cyclic sort — place each number at its "home" index
    for i in range(n):
        while (nums[i] > 0              # positive
               and nums[i] <= n          # within bounds
               and nums[nums[i] - 1] != nums[i]):  # not already placed

            # Swap nums[i] to its correct position nums[i]-1
            dest = nums[i] - 1
            nums[i], nums[dest] = nums[dest], nums[i]

    # Phase 2: Scan for first index where nums[i] != i+1
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    # All slots [1..n] are filled correctly
    return n + 1

impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        let n = nums.len();

        // Phase 1: Cyclic sort — place each number at its "home" index
        for i in 0..n {
            loop {
                let v = nums[i] as usize;
                if nums[i] <= 0              // not positive
                    || v > n               // out of bounds
                    || nums[v - 1] == nums[i]  // already placed
                {
                    break;
                }
                // Swap nums[i] to its correct position v-1
                nums.swap(i, v - 1);
            }
        }

        // Phase 2: Scan for first index where nums[i] != i+1
        for i in 0..n {
            if nums[i] != (i + 1) as i32 {
                return (i + 1) as i32;
            }
        }

        // All slots [1..n] are filled correctly
        (n + 1) as i32
    }
}

function firstMissingPositive(nums: number[]): number {
    const n = nums.length;

    // Phase 1: Cyclic sort — place each number at its "home" index
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0              // positive
            && nums[i] <= n              // within bounds
            && nums[nums[i] - 1] !== nums[i]) {  // not already placed

            // Swap nums[i] to its correct position nums[i]-1
            const dest = nums[i] - 1;
            [nums[i], nums[dest]] = [nums[dest], nums[i]];
        }
    }

    // Phase 2: Scan for first index where nums[i] != i+1
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1)
            return i + 1;
    }

    // All slots [1..n] are filled correctly
    return n + 1;
}

Step 06

Interactive Demo

Enter an array and step through the cyclic sort phase, then the scan phase.

⚙ Cyclic Sort Visualizer

nums

Press "Step →" or "Run All" to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Although there is a while loop inside a for loop, each element is swapped at most once to its correct position and never moved again. The total number of swaps across all iterations is bounded by n, making the cyclic sort phase O(n). The scan phase is another O(n) pass. No extra data structures are used.

Approach Breakdown

BRUTE FORCE

O(n) time

O(n) space

Insert all values into a HashSet in one O(n) pass, then probe 1, 2, 3, ... until a missing value is found. Each probe is O(1) and at most n+1 probes are needed. The hash set stores up to n elements, costing O(n) extra space.

OPTIMAL

O(n) time

O(1) space

Cyclic sort places each value k at index k-1 using in-place swaps. Despite the nested while-inside-for, each element is swapped at most once to its home position, bounding total swaps to n. A final linear scan finds the first mismatch -- no extra data structures needed.

🎯

The key constraint is O(1) space -- cyclic sort uses the array itself as a hash map. Place each value k at index k-1, then scan for the first mismatch. This pattern applies to many problems: #268 (Missing Number), #287 (Find Duplicate), #442 (Find All Duplicates), and #448 (Find All Missing Numbers).

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Mutating counts without cleanup

Wrong move: Zero-count keys stay in map and break distinct/count constraints.

Usually fails on: Window/map size checks are consistently off by one.

Fix: Delete keys when count reaches zero.

First MissingPositive