First Missing Positive

1. Define the problem

Given an unsorted integer array nums, return the smallest missing positive integer — the smallest number starting from 1 that does not appear anywhere in the array. You must write an algorithm that runs in O(n) time and uses O(1) auxiliary space. The trick is that the answer can never be larger than n + 1 (the array length plus one), since there are only n slots. That means every value we care about, from 1 to n, has a natural home : value v belongs at index v - 1. So instead of a hash set, we can use the array itself as storage — walk through it, and whenever a value between 1 and n is not already sitting in its own slot, swap it there. This is called cycle sort placement . After every in-range value has been shuffled to its home slot, a second pass just looks for the first slot whose value does not match its position — that gap is the missing positive.

Constraints

1 ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums_i ≤ 2³¹ - 1

Example

Inputnums = [3, 4, -1, 1]

Output2

Explanation 1 is present but 2 is not, and 2 is the smallest positive integer missing from the array.

2. Know the words first

In plain terms

In-place: Rearranging the given array itself to do the work, instead of copying values into a new hash set or array.

3. Visualize the solution

Place each value at its own index, then scan for the first gap

2-1

Statusinit

i=0: nums[0]=3 belongs at index 2, and nums[2]=-1 is not already 3 — swap them.

What happens in this step

i = 0, nums[i] = 3, home index = 3 - 1 = 2
nums[home] = nums[2] = -1 (not equal to 3)

3 is in range (1..4) and not yet in its home slot, so swap nums[0] and nums[2].

Step 1 of 6

Steps to visualize

For each position, while the value there is in range 1..n and not already in its own slot (value - 1), swap it into that slot.
Repeat the swap at the same position until the value there is out of range or already correctly placed.
Once every position holds either its correct value or an out-of-range value, scan left to right.
The first index whose value does not equal index + 1 reveals the missing positive.
If every slot matches, the answer is n + 1 — every positive from 1 to n was present.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Place each value at its own index, then scan for the first gap

2-1

Statusinit

i=0: nums[0]=3 belongs at index 2, and nums[2]=-1 is not already 3 — swap them.

What happens in this step

i = 0, nums[i] = 3, home index = 3 - 1 = 2
nums[home] = nums[2] = -1 (not equal to 3)

3 is in range (1..4) and not yet in its home slot, so swap nums[0] and nums[2].

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function firstMissingPositive(nums) {
  const n = nums.length;

  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const target = nums[i] - 1;
      [nums[i], nums[target]] = [nums[target], nums[i]];
    }
  }

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

  return n + 1;
}

Time: O(n)
Space: O(1) (in place)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [3, 4, -1, 1]`	`2`	example from the docstring
`nums = [1]`	`2`	smallest valid input: a single element
`nums = [1, 2, 0]`	`3`	every value from 1 to n is present
`nums = [7, 8, 9, 11, 12]`	`1`	every value is out of the 1..n range, so 1 is missing
`nums = [1, 1, 2, 2]`	`3`	duplicate values that must not overwrite each other incorrectly
`nums = [-1, -2, 0]`	`1`	only non-positive values, so 1 is missing

First Missing Positive