First Missing Positive

Problem Description

Given an unsorted integer array nums, return the smallest missing positive integer.

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

Examples

Constraints

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

Index as Hash Key (Cycle Sort)

If the array has length n, the first missing positive number must be in the range [1, n + 1]. This means we can use the array itself as a hash table. We iterate through the array and try to place each number x (if 1 <= x <= n) at its correct index x - 1 by swapping. Once the elements are positioned, we run a second pass. The first index i where nums[i] != i + 1 indicates that the number i + 1 is missing.

Solution 1: Cycle Sort Placement

Re-arrange elements in-place to align values with index coordinates.

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Swap nums[i] to its correct position if possible
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        // Second pass: find the first mismatch
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)
        for i in range(n):
            # Swap nums[i] to its correct position if possible
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                correct_idx = nums[i] - 1
                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

        # Find the first mismatch
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

#include <vector>
#include <utility>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // Swap nums[i] to its correct position if possible
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                std::swap(nums[i], nums[nums[i] - 1]);
            }
        }

        // Find the first mismatch
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

Complexity Analysis

• Time Complexity: O(n) because each swap places an element in its final correct index. Since an element can be swapped at most once to its final position, the total number of swaps is bounded by n.
• Space Complexity: O(1) auxiliary space as the array is re-arranged in-place.

Where It Breaks

This solution modifies the input array in-place. If the input array is read-only (immutable), we must copy it first, which consumes O(n) space and makes the O(1) space optimization impossible.

Common Mistakes

• Infinite loops in swaps: Forgetting the condition nums[nums[i] - 1] != nums[i]. If two indices contain the same number, swapping them repeatedly will lead to an infinite loop.
• Handling out-of-bound values: Attempting to swap values that are negative, zero, or larger than n, which causes an array index out of bounds exception.

Frequently Asked Questions

Why is the upper bound of the missing positive integer n + 1? If the array contains all integers from 1 to n in order, the smallest missing positive integer is n + 1. If any integer in that range is missing, the answer must be smaller than n + 1.

How does this handle duplicate elements? The check nums[nums[i] - 1] != nums[i] prevents swaps on duplicates. The duplicate values will remain in incorrect slots and get filtered out during the second validation pass.

← All Problems