← Back to DSA Animator
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.