DSA AnimatorDSA animations
First Missing Positive LC #41 Hard Array
Problem

Given an unsorted integer array nums, return the smallest missing positive integer. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is present, 2 is the first missing positive.
Example 2
Input: nums = [1,2,0]
Output: 3
Explanation: 1 and 2 are present; 3 is missing.
Constraints: 1 ≤ nums.length ≤ 105; -231 ≤ nums[i] ≤ 231 - 1
Try Examples
Custom:
Approach
Cyclic Sort
Phase 1: for each i, while nums[i] is in [1,n] and not at its correct index, swap to nums[i]-1. Phase 2: scan left to right — first i where nums[i] ≠ i+1 returns i+1. If all correct, return n+1.
Array State
Expected: index i should hold value i+1
Variables
Phase
—
i
—
nums[i]
—
Correct idx
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Phase 1: for each i, while nums[i] in [1,n] and not at correct index, swap to nums[i]-1
2
Phase 2: scan left to right, first i where nums[i] ≠ i+1 → return i+1
3
If all correct, return n+1
Time
O(n)
Space
O(1)
Why It Works

The answer is in [1, n+1]. We use the array as a hash — value v goes to index v-1. After cyclic placement, if nums[i] = i+1 for all i then [1..n] are all present and the answer is n+1. Otherwise the first mismatch reveals the missing number. Each element is moved at most once across all iterations — total swaps ≤ n.

How to solve First Missing Positive

LeetCode 41 · Hard · Arrays · Pattern: Cyclic Placement

Why the obvious approach is slow

Sorting is O(n log n), and a hash set uses O(n) space. Both break the rules.

The key idea

The answer is always between 1 and n plus 1. So use the array itself as the hash: every number x belongs at index x −1. Swap numbers into their home, ignoring anything out of range. Then the first index that does not hold its own number gives the answer.

Remember

The answer is in 1 to n plus 1, so the array can be its own hash. Place each x at index x −1, then find the first misfit.

Run the animation above on your own input, or watch the 1:37 video explanation of First Missing Positive with a dry run and Java code.

More Arrays problems