First Missing Positive
First Missing Positive is LeetCode 41 (Hard). Given an unsorted integer array nums, return the smallest missing positive integer: the smallest positive number that does not appear in nums.
- Values can be negative, zero, far larger than the array, or repeated.
- The algorithm must run in O(n) time and use O(1) extra space.
Sorting costs O(n log n) and a hash set costs O(n) memory, so neither meets both limits; the array itself has to act as the lookup table.
- 1 <= nums.length <= 10⁵
- -2³¹ <= nums[i] <= 2³¹ - 1
Intuition
The answer is always between 1 and n + 1: n numbers can cover at most 1 to n, and if they cover all of them, the answer is n + 1. So only values 1 to n matter, and each has exactly one slot: value v belongs at index v - 1.
That lets the array be its own hash table. Cyclic sort swaps every value from 1 to n into its slot, and everything else stays wherever it lands. Afterwards, the first index i that does not hold i + 1 names the first missing positive.
"Find the missing or repeated numbers in O(1) extra space", with values that belong to the range 1 to n, is the cyclic sort pattern: index v - 1 is the home of value v. Missing Number, Find All Numbers Disappeared in an Array and Find the Duplicate Number work the same way.
Approach
Before reading on: for [3, 4, -1, 1], what is the largest the answer could ever be? If you could rearrange the array freely, where would you put each value so that one scan reveals the answer?
Two ways to solve it
Swap every value from 1 to n into index v - 1, then scan for the first slot that is wrong.
- Passes: one placing pass, one scan.
- Memory: in place, nothing extra.
- Trap: stop on duplicates.
The classic answer, and easy to picture as values going home.
Replace values outside 1 to n with n + 1, then record that v is present by making nums[v - 1] negative.
- Passes: three linear scans.
- Memory: in place, nothing extra.
- Trap: always read
abs()of a value.
No swaps, and no inner loop to reason about.
Both run in O(n) time with O(1) extra space. Cyclic sort is the more common interview answer and is easier to trace, so the steps, code and live demo follow it; the sign-marking code comes after the demo.
Send each value to its slot
For each index i, while nums[i] is between 1 and n, swap it to index nums[i] - 1. Use a while, not an if: the value that comes back to i may belong somewhere else too. Values outside 1 to n stay put; they can never be the answer.
Stop on duplicates
Also stop when the target slot already holds the same value, nums[nums[i] - 1] == nums[i]. The slot's contents decide, not the index: that check is what ends the loop on a duplicate such as the second 1 in [1, 1].
Scan for the first gap
Walk the array again. At the first index where nums[i] != i + 1, the number i + 1 is missing, and every smaller positive was found, so return i + 1. If every slot holds its own value, 1 to n are all present: return n + 1.
Why it is linear
The inner loop may run several times at one index, but every swap puts one value in its final slot, and that value never moves again. So there are at most n swaps in total, plus the final scan.
First Missing Positive solution in Python | C++ | Java
i will hold the value i + 1 (the wants row). Green tiles already hold the right value.3 is in range and index 2 does not hold it yet, so swap it there. −1 comes back to index 0. Stay at index 0: the value that just arrived may need to move too.−1 is outside 1 to 4, so it can never be the answer. Leave it; it just fills a slot whose own value is missing.4 is in range and index 3 does not hold it yet, so swap it there. 1 comes back to index 1. Stay at index 1: the value that just arrived may need to move too.1 is in range and index 0 does not hold it yet, so swap it there. −1 comes back to index 1. Stay at index 1: the value that just arrived may need to move too.−1 is outside 1 to 4, so it can never be the answer. Leave it; it just fills a slot whose own value is missing.3 already sits at index 2, where it belongs. Nothing to do.4 already sits at index 3, where it belongs. Nothing to do.i + 1. Index 0 holds 1, so 1 is present.i will hold the value i + 1 (the wants row). Green tiles already hold the right value.1 already sits at index 0, where it belongs. Nothing to do.1 belongs at index 0, but that slot already holds a 1. Swapping would trade a 1 for a 1 forever, so the loop compares against the slot's contents and stops.i + 1. Index 0 holds 1, so 1 is present.i will hold the value i + 1 (the wants row). Green tiles already hold the right value.2 is in range and index 1 does not hold it yet, so swap it there. 1 comes back to index 0. Stay at index 0: the value that just arrived may need to move too.1 already sits at index 0, where it belongs. Nothing to do.2 already sits at index 1, where it belongs. Nothing to do.i + 1. Index 0 holds 1, so 1 is present.i + 1. Index 1 holds 2, so 2 is present.n + 1, is the first one missing.Negative marking
First, every value that cannot be the answer (0 or less, or above n) becomes n + 1, so all values are positive. Then each value v from 1 to n marks slot v - 1 by making it negative. The first slot still positive is the missing number.
Common pitfalls
Writing the swap target inline in Python
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
home = nums[i] - 1 nums[i], nums[home] = nums[home], nums[i]
Python assigns left to right. Once nums[i] is overwritten, nums[i] - 1 points at a different slot, so the second write lands in the wrong place. On [2, 1] the array never changes and the loop runs forever. Save the target index first.
Swapping once with if instead of while
if 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
After a swap, a new value sits at index i. In [3, 4, -1, 1], sending 4 home brings 1 to index 1; with if, that 1 never reaches index 0, and the scan returns 1 instead of 2.
Checking the index instead of the slot's contents
while 1 <= nums[i] <= n and nums[i] != i + 1:
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
On [1, 1], the 1 at index 1 is not at its own index, so it swaps with the 1 at index 0. Nothing changes, and the loop never ends.
Edge cases
[7, 8, 9, 11, 12]Nothing moves. Index 0 does not hold 1, so the answer is 1.
[2, 1]Every slot ends up correct, the scan finds no gap, and the answer is n + 1 = 3.
Complexity
First Missing Positive FAQ
Does the First Missing Positive solution modify the input array?
Yes. Both in-place methods rearrange or re-sign nums; LeetCode allows that, and O(1) extra space is not possible otherwise. If the caller needs the original array, copy it first, which costs O(n) memory.