Find All Missing Numbers
Mahabharata — The Battle Roll — All Absent Warriors from 1 to n
अनुपस्थितान् सर्वान् ज्ञातुं — स्वस्थाने नास्ति यः। तेषां नामानि लिख — युद्धाय पुनः आहूय॥
*To know all who are absent — those not in their rightful place. Write their names — summon them again to battle.*
The Story
Unlike cs-2 (one missing number), here the array contains numbers from 1 to n but may have some numbers appearing twice and others missing. Find ALL missing numbers.
For `nums = [4,3,2,7,8,2,3,1]` (n=8), the numbers 5 and 6 are missing.
**Approach 1 — Cyclic Sort:** Apply cyclic sort (cs-1). After sorting, every index i where `nums[i] ≠ i+1` is a missing number.
Trace: [4,3,2,7,8,2,3,1] → cyclic sort → [1,2,3,4,3,2,7,8] Wait — with duplicates, when nums[i] == nums[correct], we skip (i++, don't swap forever).
After sort: [1,2,3,4,3,2,7,8] - i=0: nums[0]=1=1 ✓ - i=1: nums[1]=2=2 ✓ - i=2: nums[2]=3=3 ✓ - i=3: nums[3]=4=4 ✓ - i=4: nums[4]=3≠5 → missing 5 ✓ - i=5: nums[5]=2≠6 → missing 6 ✓ - i=6: nums[6]=7=7 ✓ - i=7: nums[7]=8=8 ✓
Answer: [5, 6] ✓
**Approach 2 — Negation Marking (no cyclic sort):** For each nums[i], mark nums[abs(nums[i])-1] as negative (visited). Then indices where value is still positive are missing.
This doesn't modify positions, just marks visitation. Both approaches work, but cyclic sort gives the canonical pattern solution.
The Roll-Caller's First Instinct
Use a HashSet of all numbers in the array. Check each number 1..n, those not in the set are missing. O(n) time, O(n) space.
public List<Integer> findDisappearedNumbersBruteForce(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) seen.add(x);
List<Integer> missing = new ArrayList<>();
for (int i = 1; i <= nums.length; i++)
if (!seen.contains(i)) missing.add(i);
return missing;
}The Cyclic Sort Wisdom
public List<Integer> findDisappearedNumbers(int[] nums) {
// Cyclic sort
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
int temp = nums[i]; nums[i] = nums[correct]; nums[correct] = temp;
} else {
i++;
}
}
// Find all indices where value is wrong
List<Integer> missing = new ArrayList<>();
for (int j = 0; j < nums.length; j++)
if (nums[j] != j + 1) missing.add(j + 1);
return missing;
}Step-by-Step Walkthrough
nums=[2,2] n=2, values should be [1,2]. Cyclic sort: i=0: nums[0]=2, correct=1. nums[0]≠nums[1] (2≠2? No, both are 2!) → i++ i=1: nums[1]=2, correct=1. nums[1]==nums[1]? → i++ Array unchanged: [2,2] Scan: i=0: nums[0]=2≠1 → missing 1. i=1: nums[1]=2=2 ✓ Return [1] ✅
Deep Insight
**cs-2 vs cs-3:** - cs-2: exactly one missing, find it. Math sum is simpler. - cs-3: multiple missing possible (duplicates fill those spots). Cyclic sort is the natural solution.
**The duplicate handling:** When nums[i] == nums[correct], both positions have the same value — we'd loop forever. So we skip (i++) and leave the duplicate where it is. After sort, that index will show the wrong value (the correct number is somewhere else as a duplicate).
**Space: O(1)** — we modify the array in-place and scan it afterward. The result list doesn't count as extra space in this context.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | HashSet stores all values |
| Optimal | O(n) | O(1) | In-place cyclic sort + single scan |
Pattern Recognition
✅ Find all missing numbers in 1..n with possible duplicates ✅ Cyclic sort: place x at index x-1, skip when arr[i]==arr[correct] ✅ Scan: index i with nums[i]≠i+1 means i+1 is missing ✅ O(1) extra space **LeetCode Trigger Phrases:** → "find all numbers disappeared in an array" → "multiple missing numbers" + 1..n range → "array contains n integers in 1..n" + find missing
Bhagavad Gita 2.18
अन्तवन्त इमे देहा नित्यस्योक्ताः शरीरिणः। अनाशिनोऽप्रमेयस्य तस्माद्युध्यस्व भारत॥
These bodies are perishable, but the soul which inhabits them is eternal, indestructible, and immeasurable. Therefore fight, O Bharata.
Connection: The missing numbers are not gone — they are simply displaced, their rightful positions occupied by duplicates. Like the eternal soul that persists even when its physical form is absent from the battlefield, the missing numbers are discovered not by their presence but by the absence of their rightful claimants. Cyclic sort restores dharmic order, revealing whose seat lies empty.