Coding Interview PatternsFirst Missing Positive
HardCyclic Sort
First Missing Positive
Explanation & Solution
Description
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.
Input:nums = [1, 2, 0]
0
1
1
2
2
0
Output: 3
Explanation: The integers in range [1, 2] are all present, so the smallest missing positive is 3.
Constraints
1 <= nums.length <= 10^5-2^31 <= nums[i] <= 2^31 - 1
Approach
Cyclic Sort pattern
1. The Core Observation
- The smallest missing positive must be in the range
[1, n+1] - If all integers from 1 to n are present, the answer is n+1
- We only care about values in
[1, n]— negatives, zeros, and values > n are irrelevant
2. Phase 1 — Modified Cyclic Sort
- For each index
i, computej = nums[i] - 1 - Only swap if all three conditions hold:
1. nums[i] > 0 — value is positive
2. nums[i] <= n — value fits within array bounds
3. nums[i] !== nums[j] — not already at correct position (avoids infinite loop on duplicates)
- Skip (advance
i) otherwise
3. Phase 2 — Find the First Gap
- After the sort, scan from
k = 0ton - 1 - The first index where
nums[k] !== k + 1meansk + 1is missing - If no gap is found, the answer is
n + 1
4. Why This Handles Arbitrary Inputs
- Negative numbers and zeros are simply skipped in Phase 1
- Values greater than
nare also skipped — they can't be the answer - Duplicates in range
[1, n]are handled by thenums[i] !== nums[j]check
🧠 Key Insight
- This is "hard" not because the logic is complex, but because the O(1) space constraint rules out sorting or hash sets. Cyclic sort is the key insight that enables an in-place O(n) solution
Time
O(n)total swaps across Phase 1 is bounded by nSpace
O(1)in-place, no extra data structuresVisualization
Input:
[1, 2, 0]
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
7 steps