First Missing Positive

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.

Approach

1. 1Store nums.size() in n, because only values from 1 through n can have meaningful destinations and every larger value must be ignored.
2. 2For 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.
3. 3Swap 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.
4. 4Stop swapping when the destination already contains the current value, because moving a duplicate back and forth would make no progress and could loop forever.
5. 5After 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.
6. 6If 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

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

#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.

#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.

Common mistakesthree wrong code shapes that look plausible