Find All Duplicate Numbers
Mahabharata — The Dual Impostors — All Warriors Who Claimed Two Positions
अनेके छलकारिणः सेनायाम् — सर्वेषां नामानि ज्ञातव्यानि। एकस्य पदे यत्र द्वे — तत् सत्यं प्रकाशयेत्॥
*Many impostors in the army — all their names must be known. Where two occupy one seat — that truth must be revealed.*
The Story
Like cs-4 but multiple duplicates: an array of n integers, each in 1..n. Some numbers appear twice, others once. Find ALL duplicates.
For `nums = [4,3,2,7,8,2,3,1]`, duplicates are [2, 3].
**Approach 1 — Cyclic Sort:** Apply cyclic sort. After placing, scan: every index i where nums[i] ≠ i+1 has a duplicate (nums[i]) occupying it.
After cyclic sort: [1,2,3,4,3,2,7,8] - i=4: nums[4]=3 ≠ 5 → duplicate is 3 - i=5: nums[5]=2 ≠ 6 → duplicate is 2 Result: [3, 2]
**Approach 2 — Negation Marking:** For each nums[i], mark nums[abs(nums[i])-1] as negative (visited). If it's already negative, nums[i] is a duplicate.
For [4,3,2,7,8,2,3,1]: - i=0, val=4: mark nums[3]=-7 → [4,3,2,-7,8,2,3,1] - i=1, val=3: mark nums[2]=-2 → [4,3,-2,-7,8,2,3,1] - i=2, val=-2→abs=2: mark nums[1]=-3 → [4,-3,-2,-7,8,2,3,1] - i=3, val=-7→abs=7: mark nums[6]=-3 → [4,-3,-2,-7,8,2,-3,1] - i=4, val=8: mark nums[7]=-1 → [4,-3,-2,-7,8,2,-3,-1] - i=5, val=2→abs=2: nums[1]=-3<0 → DUPLICATE: 2! - i=6, val=-3→abs=3: nums[2]=-2<0 → DUPLICATE: 3! - i=7, val=-1→abs=1: mark nums[0]=-4
Result: [2, 3] ✓
Negation marking is elegant and doesn't need a separate pass after sort.
The Guard's First Instinct
Use a HashSet. First occurrence: add to set. Second occurrence: duplicate. O(n) time, O(n) space.
public List<Integer> findDuplicatesBruteForce(int[] nums) {
Set<Integer> seen = new HashSet<>();
List<Integer> dups = new ArrayList<>();
for (int x : nums)
if (!seen.add(x)) dups.add(x);
return dups;
}The Negation Marking Wisdom
public List<Integer> findDuplicates(int[] nums) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int idx = Math.abs(nums[i]) - 1;
if (nums[idx] < 0) {
result.add(idx + 1); // Already visited: it's a duplicate
} else {
nums[idx] = -nums[idx]; // Mark as visited
}
}
return result;
}Step-by-Step Walkthrough
nums=[1,1,2] i=0,v=1: nums[0]=1→-1 i=1,v=1: nums[0]=-1<0 → ADD 1! i=2,v=2: nums[1]=1→-1 Return [1] ✅
Deep Insight
**Why negation works as a visited marker:** Array values are in 1..n, array indices are 0..n-1. We can use the sign of nums[v-1] as a bit flag: positive=unvisited, negative=visited. This exploits the range constraint to avoid extra space.
**cs-3 vs cs-5:** - cs-3: find all MISSING numbers (values not present) - cs-5: find all DUPLICATE numbers (values present twice) Cyclic sort reveals both: after sort, indices with wrong values reveal both missing (i+1 is missing) and duplicates (nums[i] is the duplicate).
**Constraint:** Each number appears AT MOST twice. If a number could appear 3+ times, negation marking alone wouldn't suffice.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | HashSet |
| Optimal | O(n) | O(1) | Negation marking — O(1) extra (modifies input) |
Pattern Recognition
✅ Find all duplicates in 1..n range ✅ Negation marking: nums[abs(v)-1] sign = visited flag ✅ Or cyclic sort + scan ✅ Both O(n) time, O(1) extra space **LeetCode Trigger Phrases:** → "find all duplicates in array" + 1..n → "each element appears 1 or 2 times" → "O(1) extra space" + 1..n range
Bhagavad Gita 2.55
प्रजहाति यदा कामान्सर्वान्पार्थ मनोगतान्। आत्मन्येवात्मना तुष्टः स्थितप्रज्ञस्तदोच्यते॥
When a person completely casts away, O Partha, all desires of the mind, and is satisfied in the Self by the Self, then is he said to be one of steady wisdom.
Connection: Each number in the array should be satisfied in its own position — its 'self' at index value-1. The duplicate is the restless soul that cannot settle, appearing where another already resides. The negation marking algorithm exposes these restless elements: when it tries to mark a position already marked, it reveals the duplicate — the one who, unlike the steady-minded sage, cannot remain in its own dharmic home.