Find Duplicate Number
Mahabharata — Karna — The Hidden Son Who Was Also a Pandava
एको द्विधा प्रकटितः भवत्यपि न दृश्यते। चक्रपथे संगमे तु सत्यं प्रकटमेव हि॥
*One who exists in two places, though hidden, is not unseen. At the meeting point in the cycle, truth is revealed.*
The Story
Kunti carried her secret for fifty years. Before her marriage to Pandu, she had been blessed by the sage Durvasa with a mantra to call any god and bear his child. In her youthful curiosity, she had invoked the Sun God and borne Karna — radiant, golden-armored, already marked by fate.
She had set him adrift on the river Ganga, unable to keep him.
Karna grew up as Radheya, son of a charioteer. But in the great accounting of warriors at Kurukshetra, the numbers did not add up. The Pandavas were five brothers from Pandu. But there were six sons of Kunti.
"One number appears twice in my ledger," the divine accountant told Narada after the war. "The array has numbers 1 through n, but one number appears twice. Kunti's children, numbered by birth order — the values are 1 through 5 for the five Pandavas, but value 1 (the firstborn) appears at two positions: once for Karna (who should have been position 0, the eldest), and once for Yudhishthira (who was named eldest of the official Pandavas)."
"Find the duplicate without using extra memory, without sorting, and without modifying the original array," Narada challenged.
"And this is more than a bookkeeping problem," the accountant said. "The array `nums` has n+1 elements, each between 1 and n. One value is repeated. Treating the array as a linked list where `nums[i]` is the NEXT pointer from node i, the duplicate creates a cycle."
Narada saw it: index 0 points to `nums[0]`, which points to `nums[nums[0]]`, and so on. The duplicate value means two different indices both point to the same node — creating the cycle's entry point.
"This is exactly the cycle start problem!" Narada said. "The duplicate number is the node where two paths converge — it is the beginning of the cycle."
The accountant demonstrated with a small example: `nums = [1, 3, 4, 2, 2]`
Treated as a linked list (0-indexed): - Node 0 → nums[0] = 1 - Node 1 → nums[1] = 3 - Node 2 → nums[2] = 4 - Node 3 → nums[3] = 2 - Node 4 → nums[4] = 2
Following the chain: 0 → 1 → 3 → 2 → 4 → 2 → 4 → 2... Cycle! Both index 3 and index 4 point to node 2. Node 2 is the duplicate — the cycle start.
"Apply Floyd's cycle start algorithm," the accountant said:
**Phase 1:** slow = nums[0], fast = nums[nums[0]]. Move until they meet. slow: 1 → 3 → 2 → 4 → 2 fast: 3 → 2 → 2 → 2 → 2... wait, let me re-trace.
nums = [1,3,4,2,2]: indices 0,1,2,3,4 slow starts at nums[0]=1, fast starts at nums[nums[0]]=nums[1]=3 - slow=nums[1]=3, fast=nums[nums[3]]=nums[2]=4 - slow=nums[3]=2, fast=nums[nums[4]]=nums[2]=4 - slow=nums[2]=4, fast=nums[nums[4]]=nums[2]=4 Meet at 4!
**Phase 2:** Reset slow to nums[0]=1 (start), fast stays at 4. Move both 1 step: - slow=nums[1]=3, fast=nums[4]=2 - slow=nums[3]=2, fast=nums[2]=4 - slow=nums[2]=4, fast=nums[4]=2 Hmm, not meeting at 2... Let me use the correct cycle detection.
Actually the standard solution uses `slow = nums[0]` as the starting node, not index 0. Let me redo:
Entry: start=0 (conceptually the head) slow = nums[0] = 1 fast = nums[nums[0]] = nums[1] = 3
This correctly maps to the LinkedList Cycle II problem. The duplicate is the cycle entry.
"Karna is the duplicate," Narada said softly. "Two paths lead to the same soul — one through Surya, one through Radha. The algorithm finds him without disturbing a single other warrior's record."
This is the Fast & Slow Pointer technique for finding a duplicate number.
The Accountant's First Instinct
Sort the array; adjacent duplicates are visible. Or use a HashSet. Both use extra space or modify the input — prohibited by the problem constraints.
public int findDuplicateBruteForce(int[] nums) {
// Using a HashSet — O(n) space
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
return num; // Found the duplicate!
}
seen.add(num);
}
return -1; // Should never reach here
}Floyd's Wisdom via Narada
public int findDuplicate(int[] nums) {
// Phase 1: Find meeting point (slow: 1 step, fast: 2 steps)
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow]; // Follow one link
fast = nums[nums[fast]]; // Follow two links
} while (slow != fast);
// Phase 2: Find cycle start (= duplicate number)
fast = nums[0]; // Reset fast to head
while (slow != fast) {
slow = nums[slow]; // Both move one step
fast = nums[fast];
}
return slow; // Cycle start = duplicate
}
// Test case
public static void main(String[] args) {
int[] nums = {1, 3, 4, 2, 2};
System.out.println(new Solution().findDuplicate(nums)); // 2
int[] nums2 = {3, 1, 3, 4, 2};
System.out.println(new Solution().findDuplicate(nums2)); // 3
}Step-by-Step Walkthrough
nums = [1, 3, 4, 2, 2] Linked list view (index → nums[index]): 0→1, 1→3, 2→4, 3→2, 4→2 Chain from 0: 0→1→3→2→4→2→4→... cycle! ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ PHASE 1 — find meeting point slow=nums[0]=1, fast=nums[0]=1 (start both at nums[0]) Do-while: slow=nums[1]=3, fast=nums[nums[1]]=nums[3]=2 slow=nums[3]=2, fast=nums[nums[2]]=nums[4]=2 slow==fast==2 → meeting point is 2 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ PHASE 2 — find cycle start fast = nums[0] = 1 slow = 2 (still at meeting point) Step 1: slow=nums[2]=4, fast=nums[1]=3 Step 2: slow=nums[4]=2, fast=nums[3]=2 MEET at 2! ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ✅ Return 2 — the duplicate number
Deep Insight
**Why does treating the array as a linked list work?**
With n+1 values each in range [1,n], we have n+1 nodes. Since values are in [1,n], starting from index 0 and following nums[i] chains, we always stay within valid indices. The duplicate value means two indices have the same next pointer — creating a cycle. The cycle's entry point is exactly the duplicate.
**The three constraints that make this work:** 1. Values in [1,n] — ensures we never follow index 0 (the "head") twice from a value 2. One duplicate — guarantees exactly one cycle 3. n+1 elements — pigeonhole principle ensures a duplicate exists
**Why can't we start slow and fast at index 0?** Because 0 is not a valid value (values are 1 to n), so index 0 is our "virtual head" — it's only the starting point, never a cycle node.
**Constraints of this approach:** - Cannot modify array (no marking visited) - Cannot use extra space (no HashSet) - Cannot sort (would change order)
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | HashSet stores up to n values before finding duplicate |
| Optimal | O(n) | O(1) | Array treated as linked list, only two pointer variables |
Pattern Recognition
✅ Array with n+1 values in range [1, n] ✅ Find the duplicate without modifying the array ✅ O(1) space required ✅ Can model as a linked list with a cycle **LeetCode Trigger Phrases:** → "find the duplicate number" + "O(1) space" → "array of n+1 integers, each between 1 and n" → "only one repeated number"
Bhagavad Gita 2.20
न जायते म्रियते वा कदाचिन्नायं भूत्वा भविता वा न भूयः। अजो नित्यः शाश्वतोऽयं पुराणो न हन्यते हन्यमाने शरीरे॥
The soul is never born nor dies at any time. It has not come into being, does not come into being, and will not come into being. It is unborn, eternal, ever-existing, and primeval.
Connection: Karna was one soul in two positions — the eternal self that cannot be duplicated is found by tracing the cycle of fate back to its source. The duplicate in the array, like Karna's true identity, reveals itself when we follow the chain of consequences (nums[i] → next) back to the meeting point of two paths. The algorithm doesn't create extra records; it reads the truth already written in the array's own structure.