First Missing Positive
Problem Statement
Given an unsorted integer array nums, return the smallest positive integer that does not appear in nums. The algorithm must run in O(n) time and use O(1) extra space.
Input
An integer array nums that may contain negatives, zeros, duplicates, and values larger than the array length.
Output
An integer: the smallest positive value missing from the array.
Constraints
- •
1 <= nums.length <= 10^5 - •
-2^31 <= nums[i] <= 2^31 - 1 - •
The required algorithm must run in O(n) time and use O(1) extra space
Examples
Example 1
nums = [1,2,0]
3Example 2
nums = [3,4,-1,1]
2Example 3
nums = [7,8,9,11,12]
1Learning Objectives
- Use the value range **1..n** as the only range that can affect the answer before **n + 1**.
- Treat array indices as hash buckets by placing value **v** at index **v - 1**.
- Use cyclic swaps safely in the presence of duplicates and out-of-range values.
- Prove that a final mismatch at index **i** means **i + 1** is missing.
Intuition
Pattern Recognition
The smallest missing positive must be between 1 and n + 1, where n is the array length. Values less than 1 and greater than n cannot occupy one of the first n positive slots, so they are irrelevant for detecting the first gap.
A hash set would make the scan easy but costs O(n) extra space. Sorting costs O(n log n). The index-as-hash pattern uses the array itself as buckets: if value v is in the useful range 1..n, its home is index v - 1. After every possible useful value is placed at home, the first index whose value is not i + 1 reveals the answer.
Common mistakes
- ×Trying to mark values larger than **n**, even though they cannot change the first missing positive before **n + 1**.
- ×Using an if instead of a while for swaps, which can leave the newly swapped value unprocessed.
- ×Forgetting the duplicate guard **nums[nums[i] - 1] != nums[i]**, causing an infinite swap loop.
- ×Returning **nums[i] + 1** on mismatch instead of returning the expected value **i + 1**.
Algorithm Explanation
Key idea
For an array of length n, place each useful value v in 1..n at index v - 1. Duplicates, negatives, zeros, and values greater than n are ignored. Once the placement pass stabilizes, index 0 should hold 1, index 1 should hold 2, and so on. The first broken position is the first missing positive.
Walkthrough
For nums = [3,4,-1,1], index 0 holds 3, whose home is index 2. Swap to get [-1,4,3,1]. Index 0 now has -1, so move on. Index 1 holds 4, whose home is index 3. Swap to get [-1,1,3,4]. Index 1 now holds 1, whose home is index 0. Swap to get [1,-1,3,4]. The placement pass is done. Scanning from the left, index 0 correctly has 1, but index 1 does not have 2, so the answer is 2.
Algorithm
- Let n = nums.length.
- For each index, while nums[index] is in 1..n and is not already at its home, swap it with the value at nums[index] - 1.
- Continue the while loop because the new value at this index may also need to move.
- After placement, scan index 0 through n - 1.
- Return index + 1 at the first position where nums[index] != index + 1.
- If every position is correct, return n + 1.
Solutions
Solution: Index-as-hash cyclic placement
The array becomes a compact hash table for the values 1..n. Each swap moves at least one useful value into its final home, so even though there is a nested while loop, the total number of swaps is linear.
Step-by-step
- Iterate over every index in the array.
- While the current value is useful and not already sitting in its target position, swap it into that target position.
- Use the duplicate guard to avoid swapping equal values forever.
- After all useful values have been placed, scan for the first index that does not contain its expected value.
- Return the expected value at that mismatch, or n + 1 if all slots are filled.
O(n)
O(1)
Each successful swap puts one value into its final index, so the total work across all while loops is linear.
Java implementation
Dry Run
Sample input
nums = [3,4,-1,1]. Place each useful value v at index v - 1, then scan for the first missing slot.
| step | index | value inspected | action | array after action |
|---|---|---|---|---|
| 1 | 0 | 3 | swap with index 2 | [-1,4,3,1] |
| 2 | 0 | -1 | out of range, move on | [-1,4,3,1] |
| 3 | 1 | 4 | swap with index 3 | [-1,1,3,4] |
| 4 | 1 | 1 | swap with index 0 | [1,-1,3,4] |
| 5 | 1 | -1 | out of range, move on | [1,-1,3,4] |
| 6 | scan index 0 | 1 | correct value for positive 1 | [1,-1,3,4] |
| 7 | scan index 1 | -1 | expected 2, so return 2 | [1,-1,3,4] |
After cyclic placement, the first broken slot is index 1. Since index 1 should contain 2, the first missing positive is 2.
Interview Tips
Start by narrowing the only relevant answer range to 1..n + 1. Then describe the array as a hash table where value v belongs at index v - 1. Interviewers care most about the duplicate guard and the reason the nested while loop is still O(n): every successful swap fixes a useful value into its home.
Likely follow-ups
- How would you solve it if O(n) extra space were allowed?
- How would the approach change if the array could not be modified?
- How would you find the first missing nonnegative integer instead?
- How would you return all missing positives in the range **1..n**?
Similar Problems
Key Takeaways
- The first missing positive can only be in **1..n + 1**.
- Index **v - 1** is the natural home for value **v**.
- A while loop is required because a swap may bring another useful value into the current index.
- The duplicate guard prevents infinite swapping when equal values target the same home.