83. First Missing Positive
🔗 LeetCode Problem: 41. First Missing Positive
📊 Difficulty: Hard (but Medium with Cyclic Sort!)
🏷️ Topics: Array, Hash Table
Problem Statement
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 = [1,2,0]
Output: 3
Explanation:
Numbers present: 1, 2
First missing positive: 3
Example 2:
Input: nums = [3,4,-1,1]
Output: 2
Explanation:
Numbers present: -1, 1, 3, 4
First missing positive: 2
Example 3:
Input: nums = [7,8,9,11,12]
Output: 1
Explanation:
All numbers are > 5
First missing positive: 1
Constraints:
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
🌟 ELI5: Building Intuition Step-by-Step!
🎯 Part 1: Understanding the Problem
What are we looking for?
Not just ANY missing number...
The FIRST missing POSITIVE integer!
Positive integers: 1, 2, 3, 4, 5, ...
(NOT 0, NOT negative!)
Examples:
[1, 2, 3] → First missing is 4
[1, 3, 4] → First missing is 2
[5, 6, 7] → First missing is 1
[-1, -2] → First missing is 1
Key insight:
The answer MUST be in the range [1, n+1]!
Why?
- Array has n elements
- Best case: [1, 2, 3, ..., n] → answer is n+1
- Any other case: answer is ≤ n
We only care about numbers in range [1, n]!
Anything else (0, negative, > n) is irrelevant!
🎯 Part 2: The "Parking Spots" Analogy
Think of it like numbered parking spots:
You have n parking spots numbered 1 to n
You have n cars with numbers on them
Perfect scenario:
Spot 1 → Car 1
Spot 2 → Car 2
Spot 3 → Car 3
...
Spot n → Car n
But some cars have wrong numbers (0, negative, > n)!
Example: [3, 4, -1, 1]
4 spots (indices 0-3)
Cars: 3, 4, -1, 1
Relevant cars (1 to 4): 3, 4, 1
Irrelevant: -1 (negative)
Park the relevant cars:
Car 1 → Spot 1 (index 0)
Car 3 → Spot 3 (index 2)
Car 4 → Spot 4 (index 3)
Spot 2 (index 1) → EMPTY!
First empty spot is 2! ✓
🎯 Part 3: The Cyclic Sort Trick
Core idea:
Use array indices as "spots" for numbers!
Mapping:
Number 1 → Index 0
Number 2 → Index 1
Number 3 → Index 2
...
Number i → Index i-1
After sorting:
nums[0] should be 1
nums[1] should be 2
nums[2] should be 3
...
First index where nums[i] != i+1 → answer is i+1!
Visual example: [3, 4, -1, 1]
Initial array:
Index: 0 1 2 3
Value: 3 4 -1 1
Step 1: Process index 0 (value 3)
3 should be at index 2
Swap nums[0] with nums[2]
[-1, 4, 3, 1]
Step 2: Process index 0 (value -1)
-1 is not in range [1, n], skip
Move to next
Step 3: Process index 1 (value 4)
4 should be at index 3
Swap nums[1] with nums[3]
[-1, 1, 3, 4]
Step 4: Process index 1 (value 1)
1 should be at index 0
Swap nums[1] with nums[0]
[1, -1, 3, 4]
Step 5: Continue for remaining...
Final: [1, -1, 3, 4]
Check each index:
Index 0: nums[0] = 1 (expected 1) ✓
Index 1: nums[1] = -1 (expected 2) ✗
First mismatch at index 1!
Answer: 1 + 1 = 2 ✓
🎯 Part 4: Why This is "Hard" (And How Cyclic Sort Makes It Easy!)
The challenges:
Challenge 1: Can't use extra space
❌ Can't create a HashSet to track numbers
✓ Use array itself as "hash table"
Challenge 2: Array has negatives and out-of-range
❌ Can't use simple cyclic sort
✓ Skip invalid numbers
Challenge 3: Need O(n) time
❌ Can't sort normally (O(n log n))
✓ Cyclic sort is O(n)
Challenge 4: Numbers can be anywhere
Example: [100, 200, 300]
❌ These are all > n, useless!
✓ Answer is 1
Cyclic Sort Solution:
1. Ignore numbers outside [1, n]
2. Place each valid number at its "spot"
3. First spot with wrong number → that's the answer!
4. If all spots correct → answer is n+1
All in O(n) time, O(1) space! ✓
🎨 Visual Understanding
The Problem Visualized
Example 1: nums = [1, 2, 0]
Range of interest: [1, 2, 3] (since n=3)
Present: 1, 2
Missing from range: 3
Answer: 3 ✓
Example 2: nums = [3, 4, -1, 1]
Range of interest: [1, 2, 3, 4] (since n=4)
Present: 1, 3, 4
Not in range: -1
Missing from range: 2
Answer: 2 ✓
Example 3: nums = [7, 8, 9, 11, 12]
Range of interest: [1, 2, 3, 4, 5] (since n=5)
Present: None in range!
All numbers > 5
Missing: 1, 2, 3, 4, 5
First missing: 1 ✓
The Cyclic Sort Process
Goal: Place number i at index i-1
Example: [3, 4, -1, 1]
Index: 0 1 2 3
Valid range: [1, 4]
Step-by-step:
Start: [3, 4, -1, 1]
↑
Position 0, value 3:
3 should be at index 2
Swap with index 2
[-1, 4, 3, 1]
↑
Position 0, value -1:
-1 not in [1,4], skip
Move to next
[-1, 4, 3, 1]
↑
Position 1, value 4:
4 should be at index 3
Swap with index 3
[-1, 1, 3, 4]
↑
Position 1, value 1:
1 should be at index 0
Swap with index 0
[1, -1, 3, 4]
↑
Position 1, value -1:
-1 not in [1,4], skip
Move to next
[1, -1, 3, 4]
↑
Position 2, value 3:
3 should be at index 2 ✓
Already correct!
Move to next
Position 3, value 4:
4 should be at index 3 ✓
Already correct!
Done!
Final: [1, -1, 3, 4]
Find first mismatch:
Index 0: 1 == 1 ✓
Index 1: -1 != 2 ✗
Answer: 2 ✓
🎯 Approach: Cyclic Sort ⭐
Implementation
/**
* Cyclic Sort - Place valid numbers at correct indices
* Time: O(n), Space: O(1)
*/
public int firstMissingPositive(int[] nums) {
int i = 0;
int n = nums.length;
// STEP 1: Cyclic sort - place each valid number at correct index
while (i < n) {
int correctIndex = nums[i] - 1; // Number k should be at index k-1
// Only swap if:
// 1. Number is in valid range [1, n]
// 2. Number is not already at correct position
if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
i++;
}
}
// STEP 2: Find first index where nums[i] != i+1
for (i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1; // First missing positive
}
}
// STEP 3: All positions correct, so answer is n+1
return n + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
⏰ Time: O(n) - Each number swaps at most once
💾 Space: O(1) - In-place sorting
🔍 Super Detailed Dry Run
Example: nums = [3, 4, -1, 1]
Goal: Find first missing positive (answer: 2)
n = 4
Valid range: [1, 4]
═══════════════════════════════════════════════════════════════
STEP 1: Cyclic Sort
═══════════════════════════════════════════════════════════════
Initial: [3, 4, -1, 1]
Index: 0 1 2 3
i = 0:
nums[0] = 3
correctIndex = 3 - 1 = 2
Check conditions:
nums[0] > 0? 3 > 0 ✓
nums[0] <= n? 3 <= 4 ✓
nums[0] != nums[2]? 3 != -1 ✓
All conditions met, SWAP!
Swap nums[0] with nums[2]
Array: [-1, 4, 3, 1]
i stays at 0
i = 0 (check new value):
nums[0] = -1
correctIndex = -1 - 1 = -2
Check conditions:
nums[0] > 0? -1 > 0 ✗
Condition failed (negative), i++
Array: [-1, 4, 3, 1]
i = 1
i = 1:
nums[1] = 4
correctIndex = 4 - 1 = 3
Check conditions:
nums[1] > 0? 4 > 0 ✓
nums[1] <= n? 4 <= 4 ✓
nums[1] != nums[3]? 4 != 1 ✓
All conditions met, SWAP!
Swap nums[1] with nums[3]
Array: [-1, 1, 3, 4]
i stays at 1
i = 1 (check new value):
nums[1] = 1
correctIndex = 1 - 1 = 0
Check conditions:
nums[1] > 0? 1 > 0 ✓
nums[1] <= n? 1 <= 4 ✓
nums[1] != nums[0]? 1 != -1 ✓
All conditions met, SWAP!
Swap nums[1] with nums[0]
Array: [1, -1, 3, 4]
i stays at 1
i = 1 (check new value):
nums[1] = -1
Check conditions:
nums[1] > 0? -1 > 0 ✗
Condition failed, i++
Array: [1, -1, 3, 4]
i = 2
i = 2:
nums[2] = 3
correctIndex = 3 - 1 = 2
Check conditions:
nums[2] > 0? 3 > 0 ✓
nums[2] <= n? 3 <= 4 ✓
nums[2] != nums[2]? 3 != 3 ✗
Already at correct position! i++
Array: [1, -1, 3, 4]
i = 3
i = 3:
nums[3] = 4
correctIndex = 4 - 1 = 3
Check conditions:
Already at correct position! i++
Array: [1, -1, 3, 4]
i = 4
i = 4, exit while loop
Final sorted array: [1, -1, 3, 4]
═══════════════════════════════════════════════════════════════
STEP 2: Find First Missing
═══════════════════════════════════════════════════════════════
Check each index:
i = 0:
nums[0] = 1
Expected: i + 1 = 0 + 1 = 1
1 == 1? Yes ✓
Continue
i = 1:
nums[1] = -1
Expected: i + 1 = 1 + 1 = 2
-1 == 2? No ✗
First mismatch!
Return 2 ✓
Result: 2
Example 2: nums = [1, 2, 0]
n = 3
Valid range: [1, 3]
Initial: [1, 2, 0]
Cyclic Sort:
i = 0: nums[0] = 1, correctIndex = 0
Already at correct position! i++
i = 1: nums[1] = 2, correctIndex = 1
Already at correct position! i++
i = 2: nums[2] = 0
0 not in range [1, 3] (0 > 0 fails)
i++
Final: [1, 2, 0]
Find first missing:
i = 0: nums[0] = 1, expected 1 ✓
i = 1: nums[1] = 2, expected 2 ✓
i = 2: nums[2] = 0, expected 3 ✗
Return 3 ✓
Example 3: nums = [7, 8, 9, 11, 12]
n = 5
Valid range: [1, 5]
Initial: [7, 8, 9, 11, 12]
Cyclic Sort:
i = 0: nums[0] = 7
7 > 5 (not in range), i++
i = 1: nums[1] = 8
8 > 5 (not in range), i++
i = 2: nums[2] = 9
9 > 5 (not in range), i++
i = 3: nums[3] = 11
11 > 5 (not in range), i++
i = 4: nums[4] = 12
12 > 5 (not in range), i++
Final: [7, 8, 9, 11, 12] (unchanged!)
Find first missing:
i = 0: nums[0] = 7, expected 1
7 != 1 ✗
Return 1 ✓
🎯 Why This Works - Deep Dive
The Core Insight:
═══════════════════════════════════════════════════════════════
Question: What's the answer range?
Answer MUST be in [1, n+1]!
Proof:
Best case: Array is [1, 2, 3, ..., n]
All numbers 1 to n present
First missing is n+1 ✓
Worst case: Array has no valid numbers
Example: [0, -1, -2] or [100, 200, 300]
First missing is 1 ✓
Any other case: Some numbers in [1, n] missing
Answer is somewhere in [1, n] ✓
Conclusion: We only care about numbers in [1, n]!
- Ignore 0
- Ignore negatives
- Ignore numbers > n
Why Cyclic Sort Works:
═══════════════════════════════════════════════════════════════
Strategy: Use indices as "hash table"!
Mapping:
Number 1 → Index 0
Number 2 → Index 1
Number 3 → Index 2
...
Number k → Index k-1
After sorting:
If all numbers [1, n] present:
nums = [1, 2, 3, ..., n]
Answer = n + 1
If some missing:
nums = [1, ?, 3, 4, ...]
First index with wrong value → answer!
Example: [1, -1, 3, 4]
Index 1 has -1 instead of 2
Answer: 2 ✓
Time Complexity Proof:
═══════════════════════════════════════════════════════════════
Each number swaps AT MOST once!
Why?
When we swap nums[i] to correctIndex:
That number reaches its final position
It will NEVER move again!
Example trace:
[3, 4, -1, 1]
Swap 3 to index 2: [?, ?, 3, ?]
3 is now LOCKED at index 2!
Swap 4 to index 3: [?, ?, 3, 4]
4 is now LOCKED at index 3!
Swap 1 to index 0: [1, ?, 3, 4]
1 is now LOCKED at index 0!
Total swaps: At most n
Total i increments: n
Total operations: 2n = O(n) ✓
Space Complexity:
═══════════════════════════════════════════════════════════════
No extra data structures!
Only constant variables: i, correctIndex, temp
Modify array in-place!
Space: O(1) ✓
Why Not Use HashSet?
═══════════════════════════════════════════════════════════════
HashSet approach:
Set<Integer> set = new HashSet<>();
for (int num : nums) set.add(num);
for (int i = 1; i <= n+1; i++) {
if (!set.contains(i)) return i;
}
Time: O(n) ✓
Space: O(n) ✗
Problem says O(1) space! HashSet doesn't qualify!
Cyclic Sort:
Use array itself as hash table!
Space: O(1) ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Not checking all three conditions
// ❌ WRONG - Missing range checks
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
}
Example that breaks:
nums = [0, 1, 2]
i = 0, nums[0] = 0
correctIndex = 0 - 1 = -1
Trying to access nums[-1] → CRASH!
// ✓ CORRECT - Check all conditions
if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
}
Mistake 2: Incrementing i after swap
// ❌ WRONG - Misses checking new value
if (condition) {
swap(nums, i, correctIndex);
i++; // WRONG!
}
Example that breaks:
[3, 1, 2]
Swap 3 to index 2: [2, 1, 3]
If we increment, we skip checking 2!
// ✓ CORRECT - Don't increment after swap
if (condition) {
swap(nums, i, correctIndex);
// Check the new value at i!
} else {
i++;
}
Mistake 3: Wrong final check
// ❌ WRONG - Checking if value equals index
for (int i = 0; i < n; i++) {
if (nums[i] != i) { // WRONG!
return i;
}
}
// ✓ CORRECT - Checking if value equals i+1
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
Why: Number i+1 should be at index i!
Mistake 4: Forgetting the n+1 case
// ❌ WRONG - No return at end
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// If loop completes, what to return?
// ✓ CORRECT - Return n+1 if all correct
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1; // All [1, n] present!
Mistake 5: Not handling duplicates
// ❌ WRONG - Infinite loop on duplicates
while (i < n) {
int correctIndex = nums[i] - 1;
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
}
}
Example that breaks:
[1, 1]
i = 0: nums[0] = 1, correctIndex = 0
nums[0] == nums[0]? Always true!
Never increments i → INFINITE LOOP!
// ✓ CORRECT - Include all conditions
if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
i++; // Increment for duplicates/invalid
}
🎯 Pattern Recognition
Problem Type: Find Missing Positive with Constraints
Core Pattern: Cyclic Sort with Range Validation
When to Apply:
✓ Find missing number in sequence
✓ O(1) space requirement
✓ Array can be modified
✓ Numbers might be out of range
✓ Negative numbers or zeros present
Recognition Keywords:
- "First missing positive"
- "Smallest positive integer"
- "O(1) space"
- "O(n) time"
- "Unsorted array"
Similar Problems:
- Missing Number (LC 268) - Range [0, n]
- Find Disappeared Numbers (LC 448) - Multiple missing
- Find Duplicate (LC 287) - Find extra number
Key Components:
┌────────────────────────────────────────────┐
│ Valid range: [1, n] │
│ Mapping: Number k → Index k-1 │
│ Three conditions for swap: │
│ 1. nums[i] > 0 │
│ 2. nums[i] <= n │
│ 3. nums[i] != nums[correctIndex] │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "Answer must be in range [1, n+1]"
Step 2: "Only care about numbers in [1, n]"
Step 3: "Use cyclic sort to place numbers at correct indices"
Step 4: "Number k goes to index k-1"
Step 5: "First index with wrong value is the answer"
Key Points to Mention:
- Answer range is [1, n+1]
- Ignore 0, negatives, and numbers > n
- Use array itself as hash table
- Cyclic sort: place k at index k-1
- Three conditions for valid swap
- Don't increment i after swap
- Check nums[i] != i+1 to find missing
- Return n+1 if all positions correct
- Time: O(n), Space: O(1)
Why This Approach?
"The key insight is that the answer must be in [1, n+1], so I only
need to track numbers in range [1, n]. I use cyclic sort to place
each valid number k at index k-1, using the array itself as a hash
table. After sorting, the first index where nums[i] != i+1 gives
me the answer. If all positions are correct, the answer is n+1.
This achieves O(n) time with O(1) space."
Edge Cases to Mention:
✓ All negatives/zeros → answer is 1
✓ All numbers > n → answer is 1
✓ Perfect sequence [1,2,...,n] → answer is n+1
✓ Duplicates present
✓ Single element
📝 Quick Revision Notes
🎯 Core Concept:
First Missing Positive: Answer in [1, n+1]! Only care about [1, n]. Cyclic sort: place k at index k-1. Three checks: >0, ≤n, not at correct position. Don't increment after swap! First nums[i] != i+1 is answer. All correct? Return n+1. O(n) time, O(1) space!
⚡ Quick Implementation:
class Solution {
public int firstMissingPositive(int[] a) {
// Approach - using cyclic sort
// key logic: a[i] should be present at index 'a[i] - 1'
int i = 0;
int len = a.length;
while (i < len) {
// checks - index a[i]-1 should be in the range
// same number should not be already present in the target index. Else infinite loop.
if(a[i] - 1 >= 0 && a[i] - 1 < len && a[i] != i + 1 && a[i] != a[a[i] - 1]) {
swap(a, i, a[i] - 1);
} else {
i++;
}
}
for(i = 0; i < len; i++) {
if(a[i] != i + 1) {
return i + 1;
}
}
return len + 1;
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
Solution t = new Solution();
System.out.println(t.firstMissingPositive(new int[] {3,4,-1,1}) == 2);
System.out.println(t.firstMissingPositive(new int[] {1,2,0}) == 3);
System.out.println(t.firstMissingPositive(new int[] {7,8,9,11,12}) == 1);
System.out.println(t.firstMissingPositive(new int[] {1}) == 2);
System.out.println(t.firstMissingPositive(new int[] {1, 1}) == 2);
}
}
🔑 Key Insights:
- Pattern: Cyclic Sort with validation
- Range: Answer in [1, n+1], only care about [1, n]
- Mapping: Number k → Index k-1
- Three checks: >0 AND ≤n AND not at correct position
- Critical: Don't increment i after swap!
- Find: First nums[i] != i+1
- Edge: If all correct, return n+1
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"Valid range [1,n], place at k-1, three checks, don't increment!"
Think: "Cyclic sort saves the Hard problem!" ✨
⚠️ Critical Three Conditions:
Before swapping, check ALL three:
1. nums[i] > 0 (positive)
2. nums[i] <= n (in range)
3. nums[i] != nums[correctIdx] (not already there)
Miss any? Code breaks! ✗
🧪 Edge Cases
Case 1: All negatives
Input: nums = [-1, -2, -3]
Output: 1
(No valid positives)
Case 2: Perfect sequence
Input: nums = [1, 2, 3]
Output: 4
(All present, answer is n+1)
Case 3: All out of range
Input: nums = [1000, 1001, 1002]
Output: 1
(All > n)
Case 4: Has zero
Input: nums = [0, 1, 2]
Output: 3
(0 ignored)
Case 5: Duplicates
Input: nums = [1, 1]
Output: 2
All handled correctly! ✓
Related Patterns
- Missing Number (LC 268) - Similar cyclic sort
- Find All Disappeared Numbers (LC 448) - Multiple missing
- Find Duplicate Number (LC 287) - Opposite problem
Happy practicing! 🎯
Note: This is marked HARD on LeetCode, but Cyclic Sort makes it much more approachable! The key is understanding the [1, n] range insight and the three validation conditions. Once you grasp these, the implementation is straightforward! This problem beautifully demonstrates how the right pattern can turn a Hard problem into a manageable one! 💪✨