How do you approach First Missing Positive?

The answer is always between 1 and n + 1, where n is the array length. Why? An array of n elements can cover at most the values 1..n.

What is the time complexity of First Missing Positive?

Time complexity: O(n) - amortized one placement per element. Space complexity: O(1) - the input array is reused as storage.

What are common mistakes on First Missing Positive?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

Sitelet https://gitgood.dev/coding/first-missing-positive

gitGood.dev

← Back to problems

First Missing Positive

HardAlgorithms

Description

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space (you may modify the input array).

Example 1

Input: nums = [1,2,0]

Output: 3

Explanation: The numbers 1 and 2 are present, so the answer is 3.

Example 2

Input: nums = [3,4,-1,1]

Output: 2

Explanation: 1 is present but 2 is missing.

Example 3

Input: nums = [7,8,9,11,12]

Output: 1

Explanation: The smallest positive integer 1 is missing.

Constraints

- 1 <= nums.length <= 10^5 - -2^31 <= nums[i] <= 2^31 - 1

First Missing Positive: approach, complexity and pitfalls

A hard arrays & hashing problem, graded against 7 test cases (4 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

The answer is always between 1 and n + 1, where n is the array length. Why? An array of n elements can cover at most the values 1..n.
Try to put each value v (when 1 <= v <= n) into its 'home' slot at index v - 1 by swapping. Values outside 1..n can be ignored.
After the placement pass, scan for the first index i where nums[i] != i + 1 - that i + 1 is the answer. If every slot matches, the answer is n + 1.

The optimal approach

Show the approach: Cyclic Sort (Index as Hash)

Only values in `1..n` matter, so use the array itself as a hash table: repeatedly swap `nums[i]` into its home slot `nums[i] - 1` while it's in range and the destination doesn't already hold the right value (the duplicate guard also prevents infinite swap loops). Each swap places at least one value permanently, so the total work is O(n) despite the nested loop. A final scan finds the first slot whose value isn't `i + 1`.

Time: O(n) - amortized one placement per element
Space: O(1) - the input array is reused as storage

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.