First Missing Positive — Editorial

Opening the reading…

Intuitionthe answer is hidden in the first index that cannot hold its own value

If nums has length n, the smallest missing positive must be somewhere from 1 through n + 1. Values larger than n, zero, and negative values cannot be the first missing value while every number from 1 through n is present. That means each useful value x has one natural destination: index x - 1.

Use the array itself as a presence table. Whenever nums[i] is a useful value, move it to index nums[i] - 1. After this rearrangement, index 0 should contain 1, index 1 should contain 2, and so on. The first index i whose value is not i + 1 identifies the answer immediately; if every index matches, n + 1 is missing.

Values act as addresses for their own destinations.

Approach

Store nums.size() in n, because only values from 1 through n can have meaningful destinations and every larger value must be ignored.

For each index i, repeatedly inspect nums[i] while it is in the range 1 through n, because an out-of-range value has no valid destination inside the array.

Swap nums[i] with nums[nums[i] - 1], because the current value belongs at its named index and the displaced value may also need to be placed.

Stop swapping when the destination already contains the current value, because moving a duplicate back and forth would make no progress and could loop forever.

After placement, scan from index 0 upward and return i + 1 at the first position where nums[i] is not i + 1, because that is the first positive value with no matching occupied slot.

If the second scan finds every value in its required position, return n + 1, because all positives from 1 through n are present.

Complexitythe inner loop is still amortized linear

MEASURE	BOUND	WHY
Time	O(n)	The final verification scan visits n cells. During placement, each successful swap puts a value into the index it belongs to, and a correctly occupied destination is never displaced by a later useful swap; therefore there are at most n successful swaps. The outer checks and the swaps together are O(n), even though one index contains a while loop.
Space	O(1) extra	The algorithm uses only n, i, and temporary swap storage. The input array is rearranged in place, and the returned integer is output rather than working memory, so no output storage is counted; the bound remains O(1) for every input shape.

Here n is the length of nums. No other parameter is used.

Annotated solutionC++ · in-place cyclic placement · complete judge-ready class

CPPPlace each useful value at its destination, then return the first index-value mismatch.

#include <algorithm>
#include <vector>
using namespace std;

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

The while loop is the core of the solution. A swap can bring a new value into nums[i], so checking only once would leave that new value unplaced. The loop keeps following displaced values until the current cell contains an unusable number, or its destination already contains the same value. The second condition is what makes duplicates harmless instead of endlessly swappable.

The sign-marking alternativeanother O(1)-space arrangement, useful when placement feels less natural

A different constant-space solution first removes the irrelevant values conceptually, then uses the sign of each array cell as a presence mark. After replacing every non-positive or oversized value with a harmless value such as 1, each positive value x marks index x - 1 by making that cell negative. A final scan finds the first positive cell. This is an optimisation over a hash set, not over the cyclic placement method: both already meet the required asymptotic bounds.

CPPMark the presence of each useful value through the sign of its destination cell.

#include <cstdlib>
#include <vector>
using namespace std;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int& value : nums) {
            if (value <= 0 || value > n) {
                value = 1;
            }
        }

        for (int value : nums) {
            int index = abs(value) - 1;
            nums[index] = -abs(nums[index]);
        }

        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

The marking version also mutates nums and uses two linear passes, so it has O(n) time and O(1) extra space. It may be easier to derive from the non-constant-space set solution because each value directly marks its presence. The cyclic version is often safer to implement because it never relies on preserving a value's sign while using the same array as both data and marker.