85. Find All Duplicates in an Array
🔗 LeetCode Problem: 442. Find All Duplicates in an Array
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table
Problem Statement
Given an integer array nums of length n where all the integers are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Explanation:
2 appears twice
3 appears twice
Example 2:
Input: nums = [1,1,2]
Output: [1]
Explanation:
1 appears twice
Example 3:
Input: nums = [1]
Output: []
Explanation:
No duplicates
Constraints:
- n == nums.length
- 1 <= n <= 10^5
- 1 <= nums[i] <= n
- Each element in nums appears once or twice.
🌟 ELI5: The Parking Spots Idea!
Imagine numbered parking spots:
You have 8 parking spots numbered 1-8
You have 8 cars with numbers on them
Perfect scenario:
Each car parks at its own number
Car 1 → Spot 1
Car 2 → Spot 2
...
But wait! You have: [4, 3, 2, 7, 8, 2, 3, 1]
Two "Car 2"s → Both want Spot 2!
Two "Car 3"s → Both want Spot 3!
When we try to park all cars:
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 occupied!) ← Duplicate!
Car 3 → Spot 3 (already occupied!) ← Duplicate!
Car 1 → Spot 1 ✓
Duplicates: 2 and 3! ✓
The Key Insight:
Use Cyclic Sort to place each car at its spot!
Number i should be at index i-1
When we try to swap:
If target spot already has the correct number
→ We found a duplicate!
Example:
Trying to place second "2" at index 1
But index 1 already has 2!
→ 2 is a duplicate! ✓
🎨 Visual Understanding
The Problem Visualized
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Perfect placement (what we want):
Index: 0 1 2 3 4 5 6 7
Value: 1 2 3 4 5 6 7 8
Actual array (what we have):
Index: 0 1 2 3 4 5 6 7
Value: 4 3 2 7 8 2 3 1
Numbers present:
1 (once), 2 (twice), 3 (twice), 4 (once),
7 (once), 8 (once)
Missing: 5, 6
Duplicates: 2, 3 ✓
The Cyclic Sort Process
Goal: Try to place each number at its correct index
Number i → Index i-1
When we find duplicate:
Target index already has the correct number!
Trace: [4, 3, 2, 7, 8, 2, 3, 1]
Step 1: i=0, nums[0]=4
4 should go to index 3
Swap with index 3
[7, 3, 2, 4, 8, 2, 3, 1]
Step 2: i=0, nums[0]=7
7 should go to index 6
Swap with index 6
[3, 3, 2, 4, 8, 2, 7, 1]
Step 3: i=0, nums[0]=3
3 should go to index 2
Swap with index 2
[2, 3, 3, 4, 8, 2, 7, 1]
Step 4: i=0, nums[0]=2
2 should go to index 1
Swap with index 1
[3, 2, 3, 4, 8, 2, 7, 1]
Step 5: i=0, nums[0]=3
3 should go to index 2
But nums[2] is already 3!
→ Duplicate found! (but don't add yet)
Move to next: i++
Step 6: i=1, nums[1]=2
2 should be at index 1 ✓
Already correct! i++
Step 7: i=2, nums[2]=3
3 should be at index 2 ✓
Already correct! i++
... Continue for rest ...
Final: [3, 2, 3, 4, 8, 2, 7, 1]
Now find duplicates:
Check each index i:
If nums[i] != i+1 → duplicate exists!
Index 0: nums[0]=3, expected 1 (not equal)
Index 5: nums[5]=2, expected 6 (not equal)
Wait, we need different approach for finding...
🎯 Approach 1: Hash Set (Simple)
The Most Natural Thinking 💭
Core Logic:
Use a set to track seen numbers
If we see a number again → it's a duplicate
Implementation
/**
* Using HashSet
* Time: O(n), Space: O(n)
*/
public List<Integer> findDuplicates(int[] nums) {
List<Integer> duplicates = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
duplicates.add(num); // Found duplicate!
} else {
seen.add(num);
}
}
return duplicates;
}
⏰ Time: O(n) - Single pass
💾 Space: O(n) - HashSet
❌ Problem: Uses O(n) space! Can we do O(1)?
🎯 Approach 2: Cyclic Sort (O(1) Space) ⭐
Better Approach 💡
🧠 The Core Insight
Use Cyclic Sort to place numbers at correct positions!
After sorting:
Each index i should have value i+1
If nums[i] != i+1 → that index has a duplicate
Key observation:
If 2 appears twice:
One "2" at index 1 (correct)
Other "2" somewhere else (wrong position)
The index with wrong value tells us which number is duplicate!
Implementation
/**
* Cyclic Sort - Find Duplicates
* Time: O(n), Space: O(1)
*/
public List<Integer> findDuplicates(int[] nums) {
int i = 0;
// STEP 1: Cyclic sort
while (i < nums.length) {
int correctIndex = nums[i] - 1;
// If number is not at correct position
if (nums[i] != nums[correctIndex]) {
swap(nums, i, correctIndex);
} else {
i++;
}
}
// STEP 2: Find duplicates
List<Integer> duplicates = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
// If index i doesn't have i+1, then i+1 is duplicate
if (nums[i] != i + 1) {
duplicates.add(nums[i]);
}
}
return duplicates;
}
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) - Excluding result list
🔍 Super Detailed Dry Run
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Goal: Find duplicates [2, 3]
═══════════════════════════════════════════════════════════════
STEP 1: Cyclic Sort
═══════════════════════════════════════════════════════════════
Initial: [4, 3, 2, 7, 8, 2, 3, 1]
Index: 0 1 2 3 4 5 6 7
i = 0:
nums[0] = 4
correctIndex = 4 - 1 = 3
nums[0] != nums[3]? 4 != 7? Yes, swap!
Swap nums[0] with nums[3]
Array: [7, 3, 2, 4, 8, 2, 3, 1]
i stays at 0
i = 0:
nums[0] = 7
correctIndex = 7 - 1 = 6
nums[0] != nums[6]? 7 != 3? Yes, swap!
Array: [3, 3, 2, 4, 8, 2, 7, 1]
i stays at 0
i = 0:
nums[0] = 3
correctIndex = 3 - 1 = 2
nums[0] != nums[2]? 3 != 2? Yes, swap!
Array: [2, 3, 3, 4, 8, 2, 7, 1]
i stays at 0
i = 0:
nums[0] = 2
correctIndex = 2 - 1 = 1
nums[0] != nums[1]? 2 != 3? Yes, swap!
Array: [3, 2, 3, 4, 8, 2, 7, 1]
i stays at 0
i = 0:
nums[0] = 3
correctIndex = 3 - 1 = 2
nums[0] != nums[2]? 3 != 3? No!
Already there (duplicate!)
i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
i = 1
i = 1:
nums[1] = 2
correctIndex = 2 - 1 = 1
nums[1] != nums[1]? 2 != 2? No!
Already at correct position! i++
Array: [3, 2, 3, 4, 8, 2, 7, 1]
i = 2
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
i = 3:
nums[3] = 4
Already at correct position! i++
i = 4:
nums[4] = 8
correctIndex = 8 - 1 = 7
nums[4] != nums[7]? 8 != 1? Yes, swap!
Array: [3, 2, 3, 4, 1, 2, 7, 8]
i stays at 4
i = 4:
nums[4] = 1
correctIndex = 1 - 1 = 0
nums[4] != nums[0]? 1 != 3? Yes, swap!
Array: [1, 2, 3, 4, 3, 2, 7, 8]
i stays at 4
i = 4:
nums[4] = 3
correctIndex = 3 - 1 = 2
nums[4] != nums[2]? 3 != 3? No!
Duplicate! i++
Array: [1, 2, 3, 4, 3, 2, 7, 8]
i = 5
i = 5:
nums[5] = 2
correctIndex = 2 - 1 = 1
nums[5] != nums[1]? 2 != 2? No!
Duplicate! i++
i = 6:
nums[6] = 7
Already at correct position! i++
i = 7:
nums[7] = 8
Already at correct position! i++
i = 8, exit while loop
Final sorted: [1, 2, 3, 4, 3, 2, 7, 8]
═══════════════════════════════════════════════════════════════
STEP 2: Find Duplicates
═══════════════════════════════════════════════════════════════
Check each index:
i = 0: nums[0] = 1, expected 1 (0+1) ✓
i = 1: nums[1] = 2, expected 2 (1+1) ✓
i = 2: nums[2] = 3, expected 3 (2+1) ✓
i = 3: nums[3] = 4, expected 4 (3+1) ✓
i = 4: nums[4] = 3, expected 5 (4+1) ✗
Add 3 to duplicates
i = 5: nums[5] = 2, expected 6 (5+1) ✗
Add 2 to duplicates
i = 6: nums[6] = 7, expected 7 (6+1) ✓
i = 7: nums[7] = 8, expected 8 (7+1) ✓
Duplicates: [3, 2]
Wait, expected [2, 3], got [3, 2]
Order doesn't matter! Both correct! ✓
Example 2: nums = [1, 1, 2]
Initial: [1, 1, 2]
Cyclic Sort:
i = 0: nums[0] = 1, correctIndex = 0
Already at correct position! i++
i = 1: nums[1] = 1, correctIndex = 0
nums[1] != nums[0]? 1 != 1? No!
Duplicate! i++
i = 2: nums[2] = 2, correctIndex = 1
nums[2] != nums[1]? 2 != 1? Yes, swap!
[1, 2, 1]
i stays at 2
i = 2: nums[2] = 1, correctIndex = 0
nums[2] != nums[0]? 1 != 1? No!
Duplicate! i++
Final: [1, 2, 1]
Find duplicates:
i = 0: nums[0] = 1, expected 1 ✓
i = 1: nums[1] = 2, expected 2 ✓
i = 2: nums[2] = 1, expected 3 ✗
Add 1 to duplicates
Result: [1] ✓
🎯 Approach 3: Index as Hash (Most Clever!) ⭐⭐
Even Better! 💡
🧠 The Genius Trick
Use the array ITSELF as a hash table!
Without actually sorting!
Strategy:
For each number num:
Mark index (num-1) as visited by negating it!
If index (num-1) is already negative:
→ We've seen num before → Duplicate!
Example: [4, 3, 2, 7, 8, 2, 3, 1]
Process 4: Mark index 3 negative
[4, 3, 2, -7, 8, 2, 3, 1]
Process 3: Mark index 2 negative
[4, 3, -2, -7, 8, 2, 3, 1]
Process 2: Mark index 1 negative
[4, -3, -2, -7, 8, 2, 3, 1]
Process 7: Mark index 6 negative
[4, -3, -2, -7, 8, 2, -3, 1]
Process 8: Mark index 7 negative
[4, -3, -2, -7, 8, 2, -3, -1]
Process 2: Check index 1
nums[1] is negative! → 2 is duplicate! ✓
Process 3: Check index 2
nums[2] is negative! → 3 is duplicate! ✓
Process 1: Mark index 0 negative
[-4, -3, -2, -7, 8, 2, -3, -1]
Duplicates: [2, 3] ✓
Implementation
/**
* Index as Hash - Mark with Negative
* Time: O(n), Space: O(1)
*/
public List<Integer> findDuplicates(int[] nums) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1; // Get index to mark
// If already negative, we've seen this number before
if (nums[index] < 0) {
duplicates.add(Math.abs(nums[i]));
} else {
// Mark as visited by negating
nums[index] = -nums[index];
}
}
// Optional: Restore original array
for (int i = 0; i < nums.length; i++) {
nums[i] = Math.abs(nums[i]);
}
return duplicates;
}
⏰ Time: O(n) - Single pass
💾 Space: O(1) - Modifies in place
✓ Fastest! No swapping needed!
🔍 Index-as-Hash Dry Run
Example: nums = [4, 3, 2, 7, 8, 2, 3, 1]
Strategy: Mark index (num-1) as negative
Initial: [4, 3, 2, 7, 8, 2, 3, 1]
i = 0: nums[0] = 4
index = |4| - 1 = 3
nums[3] = 7 (positive)
Mark as visited: nums[3] = -7
Array: [4, 3, 2, -7, 8, 2, 3, 1]
i = 1: nums[1] = 3
index = |3| - 1 = 2
nums[2] = 2 (positive)
Mark: nums[2] = -2
Array: [4, 3, -2, -7, 8, 2, 3, 1]
i = 2: nums[2] = -2
index = |-2| - 1 = 1
nums[1] = 3 (positive)
Mark: nums[1] = -3
Array: [4, -3, -2, -7, 8, 2, 3, 1]
i = 3: nums[3] = -7
index = |-7| - 1 = 6
nums[6] = 3 (positive)
Mark: nums[6] = -3
Array: [4, -3, -2, -7, 8, 2, -3, 1]
i = 4: nums[4] = 8
index = |8| - 1 = 7
nums[7] = 1 (positive)
Mark: nums[7] = -1
Array: [4, -3, -2, -7, 8, 2, -3, -1]
i = 5: nums[5] = 2
index = |2| - 1 = 1
nums[1] = -3 (NEGATIVE!)
Already visited! → 2 is duplicate! ✓
Add 2 to duplicates
Array: [4, -3, -2, -7, 8, 2, -3, -1]
i = 6: nums[6] = -3
index = |-3| - 1 = 2
nums[2] = -2 (NEGATIVE!)
Already visited! → 3 is duplicate! ✓
Add 3 to duplicates
Array: [4, -3, -2, -7, 8, 2, -3, -1]
i = 7: nums[7] = -1
index = |-1| - 1 = 0
nums[0] = 4 (positive)
Mark: nums[0] = -4
Array: [-4, -3, -2, -7, 8, 2, -3, -1]
Duplicates: [2, 3] ✓
Restore (optional):
Make all positive
Array: [4, 3, 2, 7, 8, 2, 3, 1]
🎯 Comparison of All Approaches
Approach Time Space Modifies Notes
═══════════════════════════════════════════════════════════════
HashSet O(n) O(n) No Simple
Cyclic Sort O(n) O(1) Yes Pattern practice
Index as Hash O(n) O(1) Yes* Fastest!
* Can restore if needed
Recommended for Interview: Index as Hash (most elegant!)
Recommended for Practice: Cyclic Sort (pattern mastery)
🎯 Why Each Approach Works
HashSet Approach:
═══════════════════════════════════════════════════════════════
Simple tracking: If we've seen number before, it's duplicate
Clear and straightforward
Only downside: O(n) space
Cyclic Sort Approach:
═══════════════════════════════════════════════════════════════
Place each number at its correct position
After sorting: duplicates occupy "wrong" positions
Key insight: Number i should be at index i-1
Positions with wrong values reveal duplicates
Index as Hash Approach:
═══════════════════════════════════════════════════════════════
Use array indices as hash table!
Mark visited by negating value at that index
If index already negative → seen before → duplicate!
Genius because:
- No swapping needed
- Single pass
- O(1) space
- Can restore if needed
⚠️ Common Mistakes
Mistake 1: Cyclic sort - forgetting duplicate check
// ❌ WRONG - Infinite loop on duplicates
while (i < n) {
int correctIdx = nums[i] - 1;
if (nums[i] != nums[correctIdx]) {
swap(nums, i, correctIdx);
}
// Missing i++!
}
// ✓ CORRECT
if (nums[i] != nums[correctIdx]) {
swap(nums, i, correctIdx);
} else {
i++; // Move past duplicate
}
Mistake 2: Index-as-hash - not using absolute value
// ❌ WRONG - Negative index!
int index = nums[i] - 1; // If nums[i] negative → crash!
// ✓ CORRECT
int index = Math.abs(nums[i]) - 1;
Mistake 3: Not checking if already negative
// ❌ WRONG - Double negation
nums[index] = -nums[index]; // If already negative → positive!
// ✓ CORRECT
if (nums[index] < 0) {
// Found duplicate
} else {
nums[index] = -nums[index];
}
📝 Quick Revision Notes
🎯 Core Concept:
Find All Duplicates: Array has [1, n], each once or twice. Three O(1) approaches: Cyclic sort (place at i-1), Index-as-hash (negate to mark), HashSet (O(n) space). Index-as-hash fastest: mark index (num-1) negative, if already negative → duplicate!
⚡ Quick Implementation (Index-as-Hash):
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> findDuplicates(int[] a) {
// Approach - cyclic sort
// key logic - at index i, number i should be present.
// checks: skip when the index where you want to replace is same. Else infinite loop.
int i = 0;
int len = a.length;
List<Integer> res = new ArrayList<>();
while (i < len) {
if(i + 1 != a[i] && 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(a[i]);
}
}
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.findDuplicates(new int[] {4,3,2,7,8,2,3,1}));
System.out.println(t.findDuplicates(new int[] {1,1,2}));
System.out.println(t.findDuplicates(new int[] {1}));
}
}
🔑 Key Insights:
- Pattern: Three approaches, all O(n) time
- Index-as-hash: Mark index (num-1) negative
- Already negative: Seen before → duplicate!
- Use Math.abs: Current value might be negative
- Cyclic sort: Place i at index i-1, wrong positions = duplicates
- Time: O(n), Space: O(1) (except HashSet)
🎪 Memory Aid:
"Mark index negative, if negative → duplicate!"
Think: "Array IS the hash table!" ✨
🧪 Edge Cases
Case 1: No duplicates
Input: nums = [1]
Output: []
Case 2: All duplicates
Input: nums = [1,1]
Output: [1]
Case 3: Multiple duplicates
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
All handled correctly! ✓
Related Patterns
- Find All Disappeared Numbers (LC 448) - Missing instead of duplicate
- Find Duplicate Number (LC 287) - Single duplicate
- Set Mismatch (LC 645) - One missing, one duplicate
Happy practicing! 🎯
Note: The Index-as-Hash approach is BRILLIANT! Using array indices as a hash table by negating values is a classic technique. This is the most elegant O(1) space solution and impresses in interviews! 💪✨