82. Find All Numbers Disappeared in an Array
🔗 LeetCode Problem: 448. Find All Numbers Disappeared in an Array
📊 Difficulty: Easy
🏷️ Topics: Array, Hash Table
Problem Statement
Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Explanation:
Numbers 1-8 should appear
Present: 1,2,3,4,7,8 (2 and 3 appear twice)
Missing: 5,6
Example 2:
Input: nums = [1,1]
Output: [2]
Explanation:
Numbers 1-2 should appear
Present: 1 (appears twice)
Missing: 2
Constraints:
- n == nums.length
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
🌟 ELI5: The Perfect Placement Idea!
Think of it like assigned parking spots:
You have 8 parking spots numbered 1-8
You have 8 cars with numbers on them
Perfect world:
Spot 1 → Car 1
Spot 2 → Car 2
Spot 3 → Car 3
...
But you have: [4, 3, 2, 7, 8, 2, 3, 1]
Let's park each car in its correct spot:
Car 4 → Spot 4 ✓
Car 3 → Spot 3 ✓
Car 2 → Spot 2 ✓
Car 7 → Spot 7 ✓
Car 8 → Spot 8 ✓
Car 2 → Spot 2 (already has Car 2!)
Car 3 → Spot 3 (already has Car 3!)
Car 1 → Spot 1 ✓
After parking, which spots are empty?
Spot 5 and Spot 6!
These are the missing numbers! ✓
The Key Insight:
Array indices: 0, 1, 2, 3, 4, 5, 6, 7
Numbers: 1, 2, 3, 4, 5, 6, 7, 8
Perfect mapping:
Number 1 should be at index 0
Number 2 should be at index 1
Number 3 should be at index 2
...
Number i should be at index i-1
If we can put each number at its correct index,
then any index with wrong number = missing number!
🎨 Visual Understanding
The Problem Visualized
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Range: 1 to 8
All numbers that SHOULD appear: [1, 2, 3, 4, 5, 6, 7, 8]
Numbers that DO appear: [1, 2, 3, 4, 7, 8] (with duplicates)
Missing: [5, 6]
The "Correct Position" Concept:
Number i should be at index i-1
Index: 0 1 2 3 4 5 6 7
Should: 1 2 3 4 5 6 7 8
Current: 4 3 2 7 8 2 3 1
✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗
All wrong!
After sorting to correct positions:
Index: 0 1 2 3 4 5 6 7
Should: 1 2 3 4 5 6 7 8
Result: 1 2 3 4 ? ? 7 8
✓ ✓ ✓ ✓ ✗ ✗ ✓ ✓
Indices 4 and 5 have wrong values!
Missing numbers: 5 and 6 ✓
🚨 CRITICAL INSIGHT - Cyclic Sort Pattern!
The Key Pattern!
This is the CYCLIC SORT pattern!
When you have:
- Array of n elements
- Values in range [1, n] or [0, n-1]
- Need to find missing/duplicate
Use Cyclic Sort:
1. Put each number at its correct index
2. Number i goes to index i-1 (or i for 0-based)
3. Swap until current position is correct
4. Move to next position
After sorting: nums[i] should equal i+1
If nums[i] != i+1 → i+1 is missing!
The Cyclic Sort Process
Original: [4, 3, 2, 7, 8, 2, 3, 1]
Index: 0 1 2 3 4 5 6 7
Step-by-step sorting process:
Start at index 0:
Current: 4 (should be at index 3)
Swap nums[0] with nums[3]
[7, 3, 2, 4, 8, 2, 3, 1]
Still at index 0 (check new value):
Current: 7 (should be at index 6)
Swap nums[0] with nums[6]
[3, 3, 2, 4, 8, 2, 7, 1]
Still at index 0:
Current: 3 (should be at index 2)
Swap nums[0] with nums[2]
[2, 3, 3, 4, 8, 2, 7, 1]
Still at index 0:
Current: 2 (should be at index 1)
Swap nums[0] with nums[1]
[3, 2, 3, 4, 8, 2, 7, 1]
Still at index 0:
Current: 3 (should be at index 2)
But nums[2] = 3 already! (duplicate)
Can't swap, move to next index
Move to index 1:
Current: 2 (should be at index 1) ✓
Already correct, move to next
Move to index 2:
Current: 3 (should be at index 2) ✓
Already correct, move to next
... Continue for all indices ...
Final sorted: [1, 2, 3, 4, 8, 2, 7, 8]
(Not perfectly sorted due to duplicates,
but each number is at correct spot OR
duplicate takes the spot)
Check each index:
Index 0: nums[0] = 1 (should be 1) ✓
Index 1: nums[1] = 2 (should be 2) ✓
Index 2: nums[2] = 3 (should be 3) ✓
Index 3: nums[3] = 4 (should be 4) ✓
Index 4: nums[4] = 8 (should be 5) ✗ → 5 is missing!
Index 5: nums[5] = 2 (should be 6) ✗ → 6 is missing!
Index 6: nums[6] = 7 (should be 7) ✓
Index 7: nums[7] = 8 (should be 8) ✓
Missing: [5, 6] ✓
🎯 Approach 1: Hash Set (Simple)
The Most Natural Thinking 💭
Core Logic:
Add all numbers to a set
Check which numbers from 1 to n are missing
Implementation
/**
* Using HashSet
* Time: O(n), Space: O(n)
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> result = new ArrayList<>();
Set<Integer> present = new HashSet<>();
// Add all numbers to set
for (int num : nums) {
present.add(num);
}
// Check which numbers are missing
for (int i = 1; i <= nums.length; i++) {
if (!present.contains(i)) {
result.add(i);
}
}
return result;
}
⏰ Time: O(n) - Two passes
💾 Space: O(n) - HashSet to store numbers
❌ Problem: Uses O(n) extra space! Violates follow-up requirement!
🎯 Approach 2: Cyclic Sort (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Cyclic Sort Pattern:
1. Place each number at its correct index
Number i goes to index i-1
2. Swap elements until current position is correct
Don't move to next until current is correct!
3. After sorting, check each index
If nums[i] != i+1, then i+1 is missing
Time: O(n), Space: O(1) ✓
Implementation
/**
* Cyclic Sort - In-Place
* Time: O(n), Space: O(1)
*/
public List<Integer> findDisappearedNumbers(int[] nums) {
int i = 0;
// STEP 1: Cyclic sort - place each number at correct index
while (i < nums.length) {
int correctIndex = nums[i] - 1; // Number i should be at index i-1
// If current number is not at correct position
// AND the correct position doesn't already have this number
if (nums[i] != nums[correctIndex]) {
// Swap to place number at correct position
swap(nums, i, correctIndex);
} else {
// Current position is correct, move to next
i++;
}
}
// STEP 2: Find missing numbers
List<Integer> result = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
// If nums[i] != i+1, then i+1 is missing
if (nums[i] != i + 1) {
result.add(i + 1);
}
}
return result;
}
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) - Only result list (doesn't count)
🔍 Super Detailed Dry Run
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Goal: Find missing numbers [5, 6]
═══════════════════════════════════════════════════════════════
STEP 1: Cyclic Sort
═══════════════════════════════════════════════════════════════
Initial:
Index: 0 1 2 3 4 5 6 7
Value: [4, 3, 2, 7, 8, 2, 3, 1]
↑
i = 0
Iteration 1 (i = 0):
nums[0] = 4
correctIndex = 4 - 1 = 3
Is nums[0] at correct position? 4 != nums[3](7)? Yes, need swap
Swap nums[0] with nums[3]
Array: [7, 3, 2, 4, 8, 2, 3, 1]
↑
i stays at 0 (check new value)
Iteration 2 (i = 0):
nums[0] = 7
correctIndex = 7 - 1 = 6
Is nums[0] at correct position? 7 != nums[6](3)? Yes, need swap
Swap nums[0] with nums[6]
Array: [3, 3, 2, 4, 8, 2, 7, 1]
↑
i stays at 0
Iteration 3 (i = 0):
nums[0] = 3
correctIndex = 3 - 1 = 2
Is nums[0] at correct position? 3 != nums[2](2)? Yes, need swap
Swap nums[0] with nums[2]
Array: [2, 3, 3, 4, 8, 2, 7, 1]
↑
i stays at 0
Iteration 4 (i = 0):
nums[0] = 2
correctIndex = 2 - 1 = 1
Is nums[0] at correct position? 2 != nums[1](3)? Yes, need swap
Swap nums[0] with nums[1]
Array: [3, 2, 3, 4, 8, 2, 7, 1]
↑
i stays at 0
Iteration 5 (i = 0):
nums[0] = 3
correctIndex = 3 - 1 = 2
Is nums[0] at correct position? 3 == nums[2](3)? YES!
Duplicate 3 is already at index 2!
Can't swap, move to next
i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
↑
i = 1
Iteration 6 (i = 1):
nums[1] = 2
correctIndex = 2 - 1 = 1
Is nums[1] at correct position? nums[1] == 2, index is 1
2 should be at index 1 ✓
Correct position! Move to next
i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
↑
i = 2
Iteration 7 (i = 2):
nums[2] = 3
correctIndex = 3 - 1 = 2
Already at correct position! i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
↑
i = 3
Iteration 8 (i = 3):
nums[3] = 4
correctIndex = 4 - 1 = 3
Already at correct position! i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
↑
i = 4
Iteration 9 (i = 4):
nums[4] = 8
correctIndex = 8 - 1 = 7
Is nums[4] at correct position? 8 != nums[7](1)? Yes, swap
Array: [3, 2, 3, 4, 1, 2, 7, 8]
↑
i stays at 4
Iteration 10 (i = 4):
nums[4] = 1
correctIndex = 1 - 1 = 0
Is nums[4] at correct position? 1 != nums[0](3)? Yes, swap
Array: [1, 2, 3, 4, 3, 2, 7, 8]
↑
i stays at 4
Iteration 11 (i = 4):
nums[4] = 3
correctIndex = 3 - 1 = 2
Is nums[4] at correct position? 3 == nums[2](3)? YES!
Duplicate! Move to next
i++
Array: [1, 2, 3, 4, 3, 2, 7, 8]
↑
i = 5
Iteration 12 (i = 5):
nums[5] = 2
correctIndex = 2 - 1 = 1
Is nums[5] at correct position? 2 == nums[1](2)? YES!
Duplicate! Move to next
i++
Array: [1, 2, 3, 4, 3, 2, 7, 8]
↑
i = 6
Iteration 13 (i = 6):
nums[6] = 7
Already at correct position! i++
Iteration 14 (i = 7):
nums[7] = 8
Already at correct position! i++
i = 8, exit while loop
Final sorted array:
Index: 0 1 2 3 4 5 6 7
Value: [1, 2, 3, 4, 3, 2, 7, 8]
═══════════════════════════════════════════════════════════════
STEP 2: Find Missing Numbers
═══════════════════════════════════════════════════════════════
Check each index:
i = 0: nums[0] = 1, should be 1 (0+1) ✓
i = 1: nums[1] = 2, should be 2 (1+1) ✓
i = 2: nums[2] = 3, should be 3 (2+1) ✓
i = 3: nums[3] = 4, should be 4 (3+1) ✓
i = 4: nums[4] = 3, should be 5 (4+1) ✗ → Add 5
i = 5: nums[5] = 2, should be 6 (5+1) ✗ → Add 6
i = 6: nums[6] = 7, should be 7 (6+1) ✓
i = 7: nums[7] = 8, should be 8 (7+1) ✓
Result: [5, 6] ✓
🎯 Why This Works - Deep Dive
The Cyclic Sort Magic:
═══════════════════════════════════════════════════════════════
Key insight: Each number swaps AT MOST ONCE!
When we swap nums[i] with nums[correctIndex]:
- We're placing nums[i] at its correct final position
- That number will NEVER move again!
- We don't increment i, so we check the new value
Example:
[4, 3, 2, 1]
↑
4 goes to index 3: [1, 3, 2, 4]
↑
1 goes to index 0: [1, 3, 2, 4]
1 is now at index 0 FOREVER! ✓
Each number takes at most 1 swap to reach correct position!
Time Complexity Proof:
═══════════════════════════════════════════════════════════════
Total swaps = Total numbers that need to move
= At most n swaps
Why? Each swap places one number at correct position forever!
Even though we have nested loop appearance:
while (i < n) {
if (needs swap) {
swap(); // Don't increment i
} else {
i++;
}
}
Total operations = n increments + at most n swaps = O(n) ✓
Why Don't We Increment i After Swap:
═══════════════════════════════════════════════════════════════
After swapping, we get a NEW number at index i!
We need to check this new number!
Example:
[4, 3, 2, 1]
↑ i = 0
Swap 4 to index 3: [1, 3, 2, 4]
↑ i = 0 (same!)
Now we have 1 at index 0
If we incremented i, we'd miss placing 1!
Check 1: it's already at correct position!
Now increment i ✓
The Duplicate Handling:
═══════════════════════════════════════════════════════════════
What if nums[i] == nums[correctIndex]?
Both positions have the same number!
This is a duplicate!
We can't swap (would do nothing)
So we just move to next index
Later, when checking, this index will show as missing
because it has the duplicate instead of its correct value!
Example:
[2, 2]
↑
2 wants to go to index 1
But nums[1] = 2 already!
Can't swap, move to next
Final: [2, 2]
Check: nums[0] = 2, should be 1 → 1 is missing ✓
Why This Pattern Works For This Problem:
═══════════════════════════════════════════════════════════════
Perfect conditions:
1. n elements
2. Values in range [1, n]
3. Can modify array
This creates perfect 1-to-1 mapping:
Number i → Index i-1
After sorting:
- Correct numbers: nums[i] = i+1
- Missing numbers: nums[i] != i+1
The indices with wrong values reveal missing numbers! ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Incrementing i after swap
// ❌ WRONG - Misses checking new value
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
i++; // WRONG! New value not checked!
}
// ✓ CORRECT - Check new value
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
// Don't increment! Check new value at i
} else {
i++; // Only increment when position is correct
}
Mistake 2: Wrong condition check
// ❌ WRONG - Checks value against index
if (nums[i] != i + 1) {
swap(...);
}
// ✓ CORRECT - Checks if value is at correct position
if (nums[i] != nums[correctIndex]) {
swap(...);
}
Mistake 3: Infinite loop on duplicates
// ❌ WRONG - Infinite loop!
while (i < nums.length) {
int correctIndex = nums[i] - 1;
if (nums[i] != correctIndex) { // Wrong check!
swap(nums, i, correctIndex);
}
}
// ✓ CORRECT - Handles duplicates
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
i++; // Move past duplicate
}
Mistake 4: Using nums[i] == i condition
// ❌ WRONG - Off by one!
if (nums[i] == i) {
i++;
}
// ✓ CORRECT - Number i should be at index i-1
if (nums[i] == i + 1) {
// Correct position
}
Mistake 5: Not handling out of range
// ❌ POTENTIAL BUG - What if nums[i] > n or < 1?
int correctIndex = nums[i] - 1;
swap(nums, i, correctIndex); // Could be out of bounds!
// ✓ CORRECT - Problem guarantees 1 <= nums[i] <= n
// So no need to check, but good to be aware!
🎯 Pattern Recognition
Problem Type: Find Missing Numbers in Range [1, n]
Core Pattern: Cyclic Sort
When to Apply:
✓ Array has n elements
✓ Values in range [1, n] or [0, n-1]
✓ Find missing/duplicate numbers
✓ Can modify array (in-place)
✓ Need O(1) space
Recognition Keywords:
- "Range [1, n]"
- "n elements"
- "Find missing numbers"
- "Find duplicates"
- "In-place" or "constant space"
Similar Problems:
- Missing Number (LC 268)
- Find All Duplicates (LC 442)
- First Missing Positive (LC 41)
- Set Mismatch (LC 645)
- Find Duplicate Number (LC 287) - uses Floyd's instead
Key Components:
┌────────────────────────────────────────────┐
│ While loop (not for!) │
│ correctIndex = nums[i] - 1 │
│ Swap if not at correct position │
│ Don't increment i after swap! │
│ Check final array for missing │
│ Time: O(n), Space: O(1) │
└────────────────────────────────────────────┘
This is the CYCLIC SORT pattern!
🧠 Interview Strategy
Step 1: "This is a cyclic sort problem!"
Step 2: "Place each number at its correct index"
Step 3: "Number i goes to index i-1"
Step 4: "After sorting, check for mismatches"
Step 5: "O(n) time, O(1) space"
Key Points to Mention:
- Cyclic sort pattern recognition
- Each number has a "correct" index
- Number i should be at index i-1
- Swap until current position is correct
- DON'T increment i after swap (critical!)
- Each number swaps at most once
- Duplicates handled automatically
- After sorting: nums[i] != i+1 means i+1 is missing
- Time: O(n) despite nested loop appearance
- Space: O(1) excluding result
Why This Approach?
"This problem has the perfect setup for cyclic sort: n elements
with values in [1, n]. I can use the values themselves as
indices by placing each number i at index i-1. I use a while
loop instead of for, because after swapping, I need to check
the new value at the same position - I don't increment until
the current position has its correct value. This ensures each
number swaps at most once, giving O(n) time. After sorting,
any index i where nums[i] != i+1 indicates that i+1 is missing."
Why Not Increment i After Swap?
"When I swap, I bring a new value to index i. I need to place
this new value in its correct position too. If I incremented i,
I'd skip checking this new value and it might end up in the
wrong place. I only increment when the current position has
its correct value."
Edge Cases to Mention:
✓ All numbers present (return empty)
✓ All numbers missing (duplicates only)
✓ Single element
✓ Consecutive duplicates
📝 Quick Revision Notes
🎯 Core Concept:
Find Missing Numbers: Use Cyclic Sort! Place number i at index i-1. Swap until correct, then don't increment i! Check new value. After sorting: if nums[i] != i+1, then i+1 is missing. Each swap fixes one position forever. O(n) time, O(1) space!
⚡ Quick Implementation:
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> findDisappearedNumbers(int[] a) {
List<Integer> res = new ArrayList<>();
// Approach 1 - using a hashset
// Approach 2 - using cyclic sort
int i = 0;
int len = a.length;
while (i < len) {
// if a number is duplicate, where you are trying to replace, there
// already exists a number. That is where, we are checking numbers at
// indices i and a[i] - 1. Same indices are being passed in swap function.
if(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) {
res.add(i + 1);
}
}
return res;
}
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.findDisappearedNumbers(new int[] {4,3,2,7,8,2,3,1}));
System.out.println(t.findDisappearedNumbers(new int[] {1,1}));
}
}
🔑 Key Insights:
- Pattern: Cyclic Sort (perfect for range [1,n])
- Mapping: Number i → Index i-1
- While loop: Not for! (need to check new values)
- Critical: Don't increment i after swap!
- Swap: Only if nums[i] != nums[correctIndex]
- Duplicate: If nums[i] == nums[correctIndex], move on
- Each number: Swaps at most once!
- After sort: nums[i] != i+1 means i+1 missing
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"While not for! Swap, don't increment! Each number once!"
Think: "Place at i-1, swap till right, missing shows!" 🔄
💡 The Key Insight:
Why don't we increment after swap?
Before: [4, 3, 2, 1]
↑ i=0
Swap 4 to index 3:
After: [1, 3, 2, 4]
↑ i=0 (same!)
New value 1 needs to be checked!
If we incremented, we'd miss it! ✗
Check 1, it's at correct position!
NOW increment i ✓
⚠️ Critical Details:
1. Use while, not for loop
2. correctIndex = nums[i] - 1
3. Check: nums[i] != nums[correctIndex]
4. If true: swap (don't increment i!)
5. If false: i++ (position is correct)
6. Duplicates: nums[i] == nums[correctIndex]
7. Can't swap duplicate, just i++
8. After sort: check nums[i] == i+1
9. If not equal: i+1 is missing
10. Each number swaps ≤ 1 time → O(n)
🔥 Why O(n) Time:
Seems like nested loop → O(n²)?
NO! Each number swaps AT MOST ONCE!
When we swap nums[i] to correctIndex:
That number reaches its final position
It will NEVER move again!
Total swaps ≤ n
Total i increments = n
Total operations = O(n) ✓
Beautiful! 🎯
🧪 Edge Cases
Case 1: All numbers present
Input: nums = [1, 2, 3, 4]
Output: []
(No missing numbers)
Case 2: All numbers missing (only duplicates)
Input: nums = [1, 1, 1, 1]
Output: [2, 3, 4]
Case 3: Single element
Input: nums = [1]
Output: []
Case 4: Consecutive duplicates
Input: nums = [2, 2]
Output: [1]
Case 5: Mixed missing
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Output: [5, 6]
All handled correctly! ✓
Related Patterns
- Missing Number (LC 268) - Cyclic sort
- Find All Duplicates (LC 442) - Cyclic sort
- First Missing Positive (LC 41) - Cyclic sort variation
- Set Mismatch (LC 645) - Find missing and duplicate
Happy practicing! 🎯
Note: This is your first Cyclic Sort problem! This pattern is POWERFUL for arrays with values in a specific range. The key insight: use the values as indices! Master the "don't increment after swap" rule and you'll ace all cyclic sort problems! 🔄✨