First Missing Positive: Cyclic Sort in O(n) Time
LeetCode First Missing Positive (problem 41) asks: given an unsorted integer array nums, return the smallest missing positive integer. The catch is that your solution must run in O(n) time and use O(1) auxiliary space. No sorting. No hash sets. Just the array itself.
This is rated hard, but the core idea is surprisingly clean once you see it. You turn the input array into its own hash map.
The problem
Given nums = [3, 4, -1, 1], the answer is 2. The positive integers 1, 3, and 4 are present, but 2 is missing. For nums = [1, 2, 0], the answer is 3. For nums = [7, 8, 9, 11, 12], the answer is 1.
The answer is always in the range [1, n+1] where n is the length of the array. Why? Because even if the array contains all of 1 through n, the answer would be n+1. And if any positive integer in that range is missing, it is the answer. So you only need to worry about values between 1 and n.
Why a hash set does not qualify
The obvious solution is to dump everything into a set, then check 1, 2, 3, ... until you find one that is missing. That works in O(n) time, but it uses O(n) space for the set. The problem explicitly forbids extra space beyond O(1). You need a way to "mark" which numbers are present without allocating a separate data structure.
The key insight: the array has n slots, and the answer is always between 1 and n+1. So you can use the array itself as a hash map where value v gets stored at index v-1. That is exactly what cyclic sort does.
The approach: index-as-hash with cyclic sort
The strategy has two phases:
Phase 1: Place each number at its correct index. For every value v in the array, if v is between 1 and n, it belongs at index v-1. You swap nums[i] with nums[nums[i]-1] repeatedly until the current position holds either a value that is already correct, a value outside the range [1, n], or a duplicate.
Phase 2: Scan for the first mismatch. Walk through the array. The first index i where nums[i] != i+1 tells you that i+1 is the smallest missing positive. If every position matches, the answer is n+1.
def firstMissingPositive(nums: list[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
That is the entire solution. Two loops, no extra data structures. The first loop does all the placement work. The second loop finds the gap.
Visual walkthrough
Let's trace through nums = [3, 4, -1, 1] step by step. Watch how each value migrates to its "home" index.
Initial array
Start at i=0. nums[0]=3. It should be at index 2. Swap nums[0] and nums[2].
After swap 1: nums[0] and nums[2] swapped
Now nums[0]=-1. Negative, so skip it. Move to i=1.
i=1: nums[1]=4, should be at index 3. Swap nums[1] and nums[3].
Swap nums[1] and nums[3].
After swap 2: nums[1] and nums[3] swapped
Now nums[1]=1, which should be at index 0. Swap nums[1] and nums[0].
After swap 3: nums[1] and nums[0] swapped
Now nums[1]=-1. Negative, so skip. Move to i=2.
i=2: nums[2]=3, should be at index 2. Already in place.
nums[2] is already correct. Move to i=3. nums[3]=4, index 3 is correct too. Placement done.
Scan: find the first index where nums[i] != i+1
nums[1]=-1, but we expected 2. The answer is 2.
Three swaps are enough to place every valid positive integer. The scan then finds nums[1] = -1, which is not 2, so the answer is 2.
Why the while loop terminates
The inner while loop looks like it could run forever, but it cannot. Each swap puts at least one element into its correct position, and once an element is in its correct position, it never moves again. Since there are at most n elements, at most n swaps happen across the entire outer loop. The total work for the placement phase is O(n), not O(n^2).
The condition nums[nums[i] - 1] != nums[i] is critical. It stops the loop in two cases: when the target position already holds the correct value (meaning the element is already placed), or when there is a duplicate (swapping would not make progress). Without this guard, the loop would cycle endlessly on inputs like [1, 1].
Think of the while loop condition as asking: "Is this value in range AND not already at home?" If both are true, swap it home. If either fails, move on. This guarantees progress on every iteration.
Complexity
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) auxiliary |
Time: The outer for loop runs n times. The inner while loop performs at most n total swaps across all iterations (each swap places one value permanently). So the total work is O(n).
Space: No extra arrays, no hash sets, no recursion stack. The only variables are i, j, and n. That is O(1) auxiliary space.
The building blocks
This problem uses two reusable bricks that show up across many LeetCode problems.
Cyclic sort
Cyclic sort is the technique of placing each element at the index derived from its value. For an array that should contain values 1 through n, value v belongs at index v-1. You iterate through the array and, at each position, keep swapping until the current slot holds either its correct value or an out-of-range value.
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
j = nums[i] - 1
nums[i], nums[j] = nums[j], nums[i]
This micro-pattern appears in:
- Missing Number (LeetCode 268) where you place each value at its index and find the gap.
- Find All Numbers Disappeared in an Array (LeetCode 448) where cyclic sort reveals all missing numbers, not just the first.
- Find the Duplicate Number (LeetCode 287) where a value collision during placement reveals the duplicate.
- Set Mismatch (LeetCode 645) where one number is duplicated and one is missing.
Index-as-hash
The idea of using array indices as implicit keys instead of a separate hash map. When values are bounded by the array size, you can encode "present" or "absent" directly in the array. This avoids allocating extra space.
The index-as-hash concept shows up beyond cyclic sort:
- Product of Array Except Self stores prefix and suffix products in the output array itself, using indices as implicit keys.
- Sort Colors uses pointer positions (which are indices) to partition values into the correct regions without extra storage.
Edge cases
All negative values: nums = [-1, -2, -3]. No positive numbers exist, so none get placed. The scan finds nums[0] != 1 immediately. Answer: 1.
Sequential starting from 1: nums = [1, 2, 3, 4]. Every element is already at its correct index. The scan finds no mismatches. Answer: n+1 = 5.
Single element: nums = [1] returns 2. nums = [2] returns 1. nums = [-5] returns 1.
Duplicates: nums = [1, 1]. The first 1 goes to index 0. The second 1 tries to go to index 0 but the guard nums[nums[i]-1] != nums[i] catches the duplicate and skips it. The scan finds nums[1] != 2. Answer: 2.
Do not forget the duplicate guard. Without nums[nums[i] - 1] != nums[i], your while loop will swap the same two duplicate values back and forth infinitely. This is the most common bug in cyclic sort solutions.
From understanding to recall
Reading the explanation is step one. But in an interview, you need to produce this solution from a blank screen. The algorithm has exactly two phases: place, then scan. The placement loop has one condition with two checks (in range, not already home) and one swap. The scan is a single for loop.
The real challenge is remembering the while loop condition. Drill it. Write while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i] from scratch. Write the swap j = nums[i] - 1; nums[i], nums[j] = nums[j], nums[i]. Do it again in a few days. Then again a week later. After a few reps, the condition stops being something you memorize and becomes something you derive from the invariant: "swap if in range and not home."
Related posts
- Sort Colors - Another in-place array rearrangement where you use the array itself (with pointers as implicit boundaries) instead of extra storage. The Dutch national flag partitions by category; cyclic sort partitions by value.
- Contains Duplicate - A simpler problem where detecting duplicates is the goal. First Missing Positive handles duplicates as a side effect of the cyclic sort guard condition.