Find the Corrupt Pair
Mahabharata — The Twin Error — One Warrior Doubled, One Displaced
एकस्य अभावः, अन्यस्य द्विधा भावः। द्वयोः नामानि ज्ञात्वा त्रुटिं संशोधय॥
*One is absent, another appears twice. Know both their names — and correct the error in the roll.*
The Story
An array of n numbers should contain all integers from 1 to n. But exactly one number is duplicated (appears twice) and one is missing. Find both: return [duplicate, missing].
For `nums = [3,1,2,5,2]` (n=5): 2 appears twice, 4 is missing. Return [2, 4].
Sahadeva proposed the cyclic sort approach: 1. Apply cyclic sort (handle duplicates: if nums[i]==nums[correct], skip) 2. After sort, find the index i where nums[i] ≠ i+1 3. At that index: nums[i] is the duplicate, i+1 is the missing number
Trace for [3,1,2,5,2]: Cyclic sort: - i=0: 3→correct=2. swap→[2,1,3,5,2] - i=0: 2→correct=1. swap→[1,2,3,5,2] - i=0: 1→correct=0. match→i++ - i=1: 2→correct=1. match→i++ - i=2: 3→correct=2. match→i++ - i=3: 5→correct=4. swap→[1,2,3,2,5] - i=3: 2→correct=1. nums[3]=2==nums[1]=2 → skip→i++ - i=4: 5→correct=4. match→i++
Result: [1,2,3,2,5] Scan: i=3: nums[3]=2≠4 → duplicate=2, missing=4
Return [2, 4] ✓
This elegantly combines cs-3 (find missing) and cs-4 (find duplicate) into one pass.
The Auditor's First Instinct
Sort the array. Scan for nums[i]==nums[i+1] (duplicate) and the index where value differs by 2 (missing). O(n log n).
public int[] findErrorNumsBruteForce(int[] nums) {
Arrays.sort(nums);
int dup = -1, missing = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i-1]) dup = nums[i];
else if (nums[i] > nums[i-1]+1) missing = nums[i-1]+1;
}
if (nums[nums.length-1] != nums.length) missing = nums.length;
return new int[]{dup, missing};
}Sahadeva's Cyclic Sort Wisdom
public int[] findErrorNums(int[] nums) {
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++;
}
}
for (int j = 0; j < nums.length; j++)
if (nums[j] != j + 1) return new int[]{nums[j], j + 1};
return new int[]{-1, -1};
}Step-by-Step Walkthrough
nums=[1,2,2,4] Cyclic sort: i=0: 1→correct=0, match→i++ i=1: 2→correct=1, match→i++ i=2: 2→correct=1, nums[2]=2==nums[1]=2 → skip→i++ i=3: 4→correct=3, match→i++ Array: [1,2,2,4] Scan: i=2: nums[2]=2≠3 → return [2,3] ✅
Deep Insight
**Why exactly one mismatch?** If one number x appears twice and one number y is missing, then exactly one index (y-1) will have nums[y-1]=x instead of y. After cyclic sort, this is the single index where nums[i]≠i+1.
**Relationship to cs-3 and cs-4:** - cs-3: multiple missing, multiple indices with wrong values - cs-4: single duplicate only (one wrong index, value is the duplicate) - cs-6: one missing + one duplicate → same index tells BOTH (value=duplicate, index+1=missing)
**Alternative: Math approach** sum(nums) - n*(n+1)/2 = duplicate - missing sum(nums²) - sum(1²..n²) = duplicate² - missing² Solve system of two equations for two unknowns.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(1) | Sort + scan |
| Optimal | O(n) | O(1) | Cyclic sort + single scan |
Pattern Recognition
✅ Find [duplicate, missing] pair in 1..n range ✅ Cyclic sort: skip when nums[i]==nums[correct] ✅ Single wrong-index reveals BOTH: value=dup, index+1=missing ✅ Combines cs-3 and cs-4 in one pass **LeetCode Trigger Phrases:** → "set mismatch" (LeetCode 645) → "find duplicate and missing" in 1..n → "corrupt pair" in permutation array
Bhagavad Gita 18.78
यत्र योगेश्वरः कृष्णो यत्र पार्थो धनुर्धरः। तत्र श्रीर्विजयो भूतिर्ध्रुवा नीतिर्मतिर्मम॥
Wherever there is Krishna, the Lord of Yoga, and wherever there is Arjuna, the holder of the bow, there will surely be prosperity, victory, happiness, and sound morality.
Connection: The corrupt pair — duplicate and missing — are twin imbalances that destabilize the ordered system. Like the Gita's final verse that pairs Krishna's wisdom with Arjuna's action, the solution pairs the detection of excess (duplicate) with the detection of absence (missing). In restoring both, complete order is re-established. The algorithm returns not one truth but two — the paired correction that restores dharmic balance.