Back to solutions

First Missing Positive

HardArrays

Find the smallest missing positive integer in O(n) time, O(1) space.

Open problem
Constraints
  • 0 <= n <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1

Index placement (cyclic sort)

Time O(n)Space O(1)

The answer must lie in [1, n+1]. Place each value v in [1, n] at index v-1 by swapping. After this, scan for the first index i whose value is not i+1 that i+1 is missing. If all positions are correct, the answer is n+1. Values out of range are ignored.

Key terms
cyclic sort:
Repeatedly swapping each value to its 'home' index v-1 until everything is in place.
home index:
Value v belongs at position v-1 in a 1..n arrangement.
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;
}
Step by step
  1. For each position, while its value v is in [1, n] and not already at home (nums[v-1] != v), swap it home.
  2. Out-of-range or already-placed values stop the inner loop.
  3. Scan: the first index i where nums[i] != i+1 means i+1 is missing.
  4. If every slot matches, the answer is n+1.