41. First Missing Positive

HardArrays and HashingIn-place array as a hash tableIndex-as-hash placement (cyclic sort)

First Missing Positive

Given an unsorted integer array nums, return the smallest positive integer (starting from 1) that does not appear in the array. You must run in O(n) time and use O(1) auxiliary space.

Open official problem prompt ↗

In plain English

Find the smallest positive integer absent from the array without allocating extra memory proportional to n.

Picture it like this

Like a coat check where ticket k must hang on hook k: after everyone hangs their coat on its matching hook, the first empty hook whose number is a valid ticket tells you which ticket never showed up.

Example

Input: nums = [3, 4, -1, 1]
Output: 2
Why: 1 is present but 2 is missing, and 2 is the smallest such positive integer.

Constraints

1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1Must be O(n) time and O(1) extra space

Pattern lesson

See the pattern, then code

Index-as-hash placement (cyclic sort)

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. In an array of length n, the first missing positive can only be one of 1..n+1. Place each value v in slot v-1; whichever slot i does not hold i+1 reveals the answer.

New words, made simpleKnow these before the algorithm

Cyclic sort: Repeatedly swapping a value to the index it belongs at until the whole array is a fixed-point mapping.
In-place: Rearranging the input array itself instead of using an auxiliary structure, keeping extra space O(1).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash set membership

Correct but violates the O(1) space requirement.

Add all values to a set, then test 1, 2, 3, ... until one is missing.

Time O(n)Space O(n)

Sort then scan

Too slow; the problem mandates linear time.

Sort the array and walk it tracking the next expected positive.

Time O(n log n)Space O(1)

Best choiceIndex placement / cyclic sort

Meets both the time and space bounds using the array as a hash table.

Use each slot i to store i+1 by swapping values home, then find the first mismatch.

Time O(n)Space O(1)

The rule we keep true

Invariant

Once the placement loop passes an index, either that slot holds its correct value i+1 or the value that belongs there is not present in the array.

Why this is correct

Reasoning

Each swap moves at least one value to its final correct slot, so the total number of swaps is bounded by n, keeping the nested while loop amortized O(n). After placement, slot i holds i+1 exactly when i+1 exists in the array, so the first violated slot is precisely the smallest missing positive.

The algorithm in three movesSay these aloud before coding

1Ignore values outside 1..n; they can never be the answer

place 3 -> idx2: [-1,4,3,1]

2For each position, repeatedly swap the value v into index v-1 until the slot is correct or the value is out of range

place 4,1 -> [1,-1,3,4]

3Scan left to right for the first index i where nums[i] != i+1

idx1 holds -1 != 2 -> return 2

4Return that i+1, or n+1 if every slot is correct

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-12

1 · Readnums[0] = 3

2 · AskIs 3 in [1,4] and not already home at index 2?

3 · Update state[3,4,-1,1]

4 · ResultSwap with index 2 -> [-1,4,3,1]; nums[0]=-1 is out of range, stop.

Key takeaway

After placement each value sits at index value-1; index 1 is wrong, exposing the missing 2.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Cyclic placement
The while loop keeps swapping the current value to its home index v-1 until it is out of range or already correct, which is what makes each value land in its slot.
2
Lines 7-9Find the gap
The first index whose value is not i+1 is the smallest missing positive.
3
Lines 10Full array case
If every slot is correct the array holds 1..n, so the answer is n+1.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

All negatives or zeros, e.g. [-1,-2] -> 1
Array already 1..n contiguous, e.g. [1,2,3] -> 4
Single element [1] -> 2 and [2] -> 1
Duplicates like [1,1] -> 2 (the != guard prevents infinite swapping)

Common beginner mistakes

Writing an if instead of a while so misplaced values are not fully settled
Forgetting the nums[nums[i]-1] != nums[i] guard, causing an infinite loop on duplicates
Comparing after moving with a stale index; always re-read nums[i] each iteration
Assuming the answer can exceed n+1

Check your understanding

Why is the answer guaranteed to be within 1..n+1 for an array of length n?

First Missing Positive

First Missing Positive

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing