Find the Duplicate Number
Mahabharata — The Impostor — The Single Warrior Who Appears at Two Positions
एकः योधः द्विधा दृश्यते — तस्य नाम किम्?। यत्र द्वे एकस्य रूपे — तत्र छलं ज्ञातव्यम्॥
*One warrior appears in two places — what is his name? Where two of the same form exist — there lies the deception to be unmasked.*
The Story
An array of n+1 integers where each integer is in the range [1, n]. Exactly one number is duplicated. Find it.
Constraints: must use O(1) extra space and not modify the array (follow-up). But with cyclic sort (modifying allowed), it's elegant.
**Approach 1 — Cyclic Sort:** Apply cyclic sort. When we try to place nums[i] at its correct position and find nums[correct] == nums[i] already (duplicate detected) — THAT value is the duplicate.
For `nums = [1,3,4,2,2]`: - i=0: nums[0]=1, correct=0. Match (1==1) → i++ - i=1: nums[1]=3, correct=2. 3≠4 → swap → [1,4,3,2,2] - i=1: nums[1]=4, correct=3. 4≠2 → swap → [1,2,3,4,2] - i=1: nums[1]=2, correct=1. 2==2 Match → i++ - i=2: nums[2]=3, correct=2. Match → i++ - i=3: nums[3]=4, correct=3. Match → i++ - i=4: nums[4]=2, correct=1. nums[4]=2 == nums[1]=2 → DUPLICATE! → i++ Scan: i=4: nums[4]=2≠5 → 2 is at wrong index. Or check during sort.
Actually cleaner: after cyclic sort, find index where nums[i] ≠ i+1. The value nums[i] is the duplicate.
**Approach 2 — Floyd Cycle Detection (O(1) space, no modification):** Treat array as a linked list: node i has next pointer nums[i]. Since n+1 values in range 1..n, there must be a cycle (like fs-1/fs-2!). Use Floyd's algorithm to find the duplicate (cycle entry point).
Both approaches work. Cyclic sort is in-place O(n).
The Guard's First Instinct
Sort the array. The duplicate is any nums[i] == nums[i+1]. O(n log n).
public int findDuplicateBruteForce(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length-1; i++)
if (nums[i] == nums[i+1]) return nums[i];
return -1;
}The Cyclic Sort Wisdom
public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != i + 1) { // Not in correct position
if (nums[i] == nums[correct]) {
// Duplicate found — nums[i] is already at its correct spot
i++;
} else {
int temp = nums[i]; nums[i] = nums[correct]; nums[correct] = temp;
}
} else {
i++;
}
}
// Find the index with wrong value
for (int j = 0; j < nums.length; j++)
if (nums[j] != j + 1) return nums[j];
return -1;
}Step-by-Step Walkthrough
nums=[1,3,4,2,2] After cyclic sort: [1,2,3,4,2] Scan: i=0:1=1✓, i=1:2=2✓, i=2:3=3✓, i=3:4=4✓, i=4:2≠5 → return 2 ✅
Deep Insight
**Floyd's algorithm alternative (no modification):** Treat nums[i] as the next pointer from i. Find the entry to the cycle (like fs-2). This is the duplicate. - Phase 1: slow=nums[slow], fast=nums[nums[fast]] until they meet. - Phase 2: slow=0, both move one step at a time, meet at duplicate.
**Why cyclic sort detects duplicate:** When trying to place nums[i] at correct=nums[i]-1, if nums[correct] already equals nums[i], both positions have the same value — that's the duplicate.
**Note on problem variants:** This problem also appeared in fs-4 (Fast & Slow Pointers pattern) using Floyd's cycle detection. Both approaches solve it; the approach depends on constraints (can we modify? need O(1) space?).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(1) | Sort + scan |
| Optimal | O(n) | O(1) | Cyclic sort in-place |
Pattern Recognition
✅ Find single duplicate in 1..n range (n+1 elements) ✅ Cyclic sort: duplicate detected when nums[i]==nums[correct] ✅ Alternative: Floyd's cycle detection (O(1) no modify) ✅ Both O(n) time, O(1) space **LeetCode Trigger Phrases:** → "find duplicate number" + 1..n range → "n+1 integers, each in 1..n" → "constant space, no modification" → Floyd's
Bhagavad Gita 6.30
यो मां पश्यति सर्वत्र सर्वं च मयि पश्यति। तस्याहं न प्रणश्यामि स च मे न प्रणश्यति॥
Whoever sees Me everywhere and sees all things in Me — I am never lost to such a one, nor is that person ever lost to Me.
Connection: The duplicate is the one who appears where two should not exist — like an illusion of two where only one truth stands. The algorithm sees through the deception: when two claim the same rightful position, the truth (the duplicate) is exposed. Like the yogi who sees the one Self everywhere and is not deceived by apparent multiplicity, cyclic sort finds the single truth beneath the duplicate appearance.