Find the Duplicate Number (LeetCode 287)
You have an array nums holding n + 1 integers, every one of them in the range [1, n].
Exactly one value repeats somewhere in the array (possibly more than twice) — find and return that value.
You're required to do this without mutating nums and using only O(1) extra space.
Worked Examples
nums = [1,3,4,2,2]2nums = [3,1,3,4,2]3nums = [3,3,3,3,3]3⚖️Formal Constraints & Bounds
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nAll the integers in
numsappear only once except for precisely one integer which appears two or more times
Core Insight
Treating array indices as nodes and values as directed next pointers transforms the duplicate search into finding the entry point of a directed cycle (in-degree >= 2).
Real-World Scenario & Production Applications
Finding duplicate records or hash collisions in read-only immutable storage streams under strict O(1) memory limits.
Subproblems & Recurrence Decomposition3 Phases
Interpret array indices as graph nodes and array values nums[i] as directed next pointers. Since values are in [1, n], index 0 is a clean root with in-degree 0.
slow = nums[0]
fast = nums[0]Step-by-Step Execution Trace Table
| Phase | Step | Slow (s = nums[s]) | Fast (f = nums[nums[f]]) | Explanation | Status |
|---|---|---|---|---|---|
| Phase 1: Floyd | Init | 0 | 0 | Virtual pointer: index -> nums[index] | Start at index 0 |
| Phase 1: Floyd | 1 | nums[0] = 1 | nums[nums[0]] = nums[1] = 3 | Slow advances 1 hop, fast advances 2 hops | 1 != 3 |
| Phase 1: Floyd | 2 | nums[1] = 3 | nums[nums[3]] = nums[2] = 4 | Slow at index 3, fast at index 4 | 3 != 4 |
| Phase 1: Floyd | 3 | nums[3] = 2 | nums[nums[4]] = nums[2] = 4 | Slow at index 2, fast at index 4 | 2 != 4 |
| Phase 1: Floyd | 4 | nums[2] = 4 | nums[nums[4]] = nums[2] = 4 | Slow at index 4, fast at index 4 | Rendezvous at index 4! |
| Phase 2: Entry | Init | p1 = 0 | p2 = 4 | Reset p1 to 0, keep p2 at 4 | Both advance 1 step |
| Phase 2: Entry | 1 | nums[0] = 1 | nums[4] = 2 | p1 = 1, p2 = 2 | 1 != 2 |
| Phase 2: Entry | 2 | nums[1] = 3 | nums[2] = 4 | p1 = 3, p2 = 4 | 3 != 4 |
| Phase 2: Entry | 3 | nums[3] = 2 | nums[4] = 2 | p1 = 2, p2 = 2 | Match found! Duplicate is 2 |
| 1 | slow = nums[0] |
| 2 | fast = nums[0] |
| 3 | while True: |
| 4 | slow = nums[slow] |
| 5 | fast = nums[nums[fast]] |
| 6 | if slow == fast: |
| 7 | break |
| 8 | p1 = nums[0] |
| 9 | p2 = slow |
| 10 | while p1 != p2: |
| 11 | p1 = nums[p1] |
| 12 | p2 = nums[p2] |
| 13 | return p1 |
Conceptual Narrative
The ultimate test of Fast & Slow pointers: converting a static read-only array into an implicit directed graph where duplicate values manifest as cycle entry points.
🧭 Conceptual Foundation & Pattern Intuition
LC 287 gives you integers in the range . By Dirichlet's Pigeonhole Principle, at least one duplicate must exist. However, the problem enforces brutal constraints: you cannot modify the array (no sorting, no in-place sign negation) and you must use extra space (no hash sets, no frequency arrays).
How can we solve this in time without modifying anything? The breakthrough is recognizing an implicit functional graph:
- Every index is a node.
- The directed edge from node points to node (analogous to
node.next). - Because all values , index is never pointed to (in-degree 0) — making it the ideal unambiguous root.
- Because a duplicate value exists, at least two distinct indices point to the exact same index. In graph theory, a node with multiple incoming edges in a functional graph creates the entrance to a directed cycle!
🏟️ The Analogy: The Scavenger Hunt Clue Cards
Imagine envelopes numbered to . Inside each envelope is a slip of paper telling you which envelope to open next (nums[i]). Since all slips point to envelopes between and , envelope is the start of the hunt and nobody will ever send you back to envelope . If every clue pointed to a unique envelope, you would visit every envelope in a single path. But if two different envelopes contain the exact same clue (the duplicate number), two different paths lead to that envelope. Once you enter that room, following subsequent clues traps you in an endless loop! The envelope that started the loop is the duplicate clue card.
🔑 The Key Idea in the Code
Because nums[i] acts as the next pointer, the cycle's entrance has in-degree . That entrance node is precisely the duplicate value.
Mutating the input array: Modifying the array (e.g., negating values
nums[abs(x)] = -nums[abs(x)]or sorting) violates the problem constraint of keeping array read-only.Using
O(N)extra space: Allocating a hash set or boolean visited array violates theO(1)auxiliary space constraint.Starting search at an arbitrary index: Index 0 is guaranteed never to be part of a cycle because values are in range
[1, n]. You must initializeslow = nums[0]andfast = nums[nums[0]]to guarantee entry into the cycle.Implicit graph mapping array boundary. In LC 287 (Find the Duplicate Number), values are in range
[1, n]while indices are0..n. Index 0 has in-degree 0 (no value is 0), which guarantees that index 0 is never part of the cycle. Starting at index 0 guarantees you traverse the access road into the cycle entrance rather than starting trapped inside the cycle or cycling indefinitely.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Array of n+1 integers in [1, n] + find duplicate + no array modification + O(1) space.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: since values are in [1, n], index 0 is a guaranteed entry root; duplicates have in-degree >= 2, forming a cycle origin.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I treat the array as an implicit functional graph where index i has a directed edge to nums[i]. Since values are in [1, n], 0 is a clean starting node with in-degree 0. The duplicate value has multiple incoming edges, forming the entrance of a directed cycle. I use Floyd's cycle detection to find this entrance in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Phase 1 meets within at most N hops along the implicit functional graph. Phase 2 walks to the cycle entrance in at most N hops. Total operations <= 2N = O(N).
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Uses two integer index variables with zero array mutations.
T(N) = Phase1 + Phase2 = O(N)
Derivation Progression
Traversing indices via nums[i] closes gap by 1 each step inside cycle.
Linear traverse from root 0 and collision index meets at cycle entrance.
O(N) operations
Linear scan without allocating memory or modifying input array.
Variable Definitions
Number of elements (array length is N + 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) Integer pointers only
O(1) Integer duplicate value
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "array of n+1 integers where each integer is in range [1, n]", "only one repeated number", "do not modify the array and use only constant extra space". Implicit functional directed graph: mapping index .
. Must run in time ( optimal) and space without modifying array.
Naive modifications like marking visited indices negative violates the "do not modify array" constraint. Binary search on value range takes ; Floyd's cycle detection achieves optimal time and memory.
Find the Duplicate Number (LeetCode 287)
You have an array nums holding n + 1 integers, every one of them in the range [1, n].
Exactly one value repeats somewhere in the array (possibly more than twice) — find and return that value.
You're required to do this without mutating nums and using only O(1) extra space.
Worked Examples
nums = [1,3,4,2,2]2nums = [3,1,3,4,2]3nums = [3,3,3,3,3]3⚖️Formal Constraints & Bounds
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nAll the integers in
numsappear only once except for precisely one integer which appears two or more times
Core Insight
Treating array indices as nodes and values as directed next pointers transforms the duplicate search into finding the entry point of a directed cycle (in-degree >= 2).
Real-World Scenario & Production Applications
Finding duplicate records or hash collisions in read-only immutable storage streams under strict O(1) memory limits.
Subproblems & Recurrence Decomposition3 Phases
Interpret array indices as graph nodes and array values nums[i] as directed next pointers. Since values are in [1, n], index 0 is a clean root with in-degree 0.
slow = nums[0]
fast = nums[0]Step-by-Step Execution Trace Table
| Phase | Step | Slow (s = nums[s]) | Fast (f = nums[nums[f]]) | Explanation | Status |
|---|---|---|---|---|---|
| Phase 1: Floyd | Init | 0 | 0 | Virtual pointer: index -> nums[index] | Start at index 0 |
| Phase 1: Floyd | 1 | nums[0] = 1 | nums[nums[0]] = nums[1] = 3 | Slow advances 1 hop, fast advances 2 hops | 1 != 3 |
| Phase 1: Floyd | 2 | nums[1] = 3 | nums[nums[3]] = nums[2] = 4 | Slow at index 3, fast at index 4 | 3 != 4 |
| Phase 1: Floyd | 3 | nums[3] = 2 | nums[nums[4]] = nums[2] = 4 | Slow at index 2, fast at index 4 | 2 != 4 |
| Phase 1: Floyd | 4 | nums[2] = 4 | nums[nums[4]] = nums[2] = 4 | Slow at index 4, fast at index 4 | Rendezvous at index 4! |
| Phase 2: Entry | Init | p1 = 0 | p2 = 4 | Reset p1 to 0, keep p2 at 4 | Both advance 1 step |
| Phase 2: Entry | 1 | nums[0] = 1 | nums[4] = 2 | p1 = 1, p2 = 2 | 1 != 2 |
| Phase 2: Entry | 2 | nums[1] = 3 | nums[2] = 4 | p1 = 3, p2 = 4 | 3 != 4 |
| Phase 2: Entry | 3 | nums[3] = 2 | nums[4] = 2 | p1 = 2, p2 = 2 | Match found! Duplicate is 2 |
| 1 | slow = nums[0] |
| 2 | fast = nums[0] |
| 3 | while True: |
| 4 | slow = nums[slow] |
| 5 | fast = nums[nums[fast]] |
| 6 | if slow == fast: |
| 7 | break |
| 8 | p1 = nums[0] |
| 9 | p2 = slow |
| 10 | while p1 != p2: |
| 11 | p1 = nums[p1] |
| 12 | p2 = nums[p2] |
| 13 | return p1 |
Conceptual Narrative
The ultimate test of Fast & Slow pointers: converting a static read-only array into an implicit directed graph where duplicate values manifest as cycle entry points.
🧭 Conceptual Foundation & Pattern Intuition
LC 287 gives you integers in the range . By Dirichlet's Pigeonhole Principle, at least one duplicate must exist. However, the problem enforces brutal constraints: you cannot modify the array (no sorting, no in-place sign negation) and you must use extra space (no hash sets, no frequency arrays).
How can we solve this in time without modifying anything? The breakthrough is recognizing an implicit functional graph:
- Every index is a node.
- The directed edge from node points to node (analogous to
node.next). - Because all values , index is never pointed to (in-degree 0) — making it the ideal unambiguous root.
- Because a duplicate value exists, at least two distinct indices point to the exact same index. In graph theory, a node with multiple incoming edges in a functional graph creates the entrance to a directed cycle!
🏟️ The Analogy: The Scavenger Hunt Clue Cards
Imagine envelopes numbered to . Inside each envelope is a slip of paper telling you which envelope to open next (nums[i]). Since all slips point to envelopes between and , envelope is the start of the hunt and nobody will ever send you back to envelope . If every clue pointed to a unique envelope, you would visit every envelope in a single path. But if two different envelopes contain the exact same clue (the duplicate number), two different paths lead to that envelope. Once you enter that room, following subsequent clues traps you in an endless loop! The envelope that started the loop is the duplicate clue card.
🔑 The Key Idea in the Code
Because nums[i] acts as the next pointer, the cycle's entrance has in-degree . That entrance node is precisely the duplicate value.
Mutating the input array: Modifying the array (e.g., negating values
nums[abs(x)] = -nums[abs(x)]or sorting) violates the problem constraint of keeping array read-only.Using
O(N)extra space: Allocating a hash set or boolean visited array violates theO(1)auxiliary space constraint.Starting search at an arbitrary index: Index 0 is guaranteed never to be part of a cycle because values are in range
[1, n]. You must initializeslow = nums[0]andfast = nums[nums[0]]to guarantee entry into the cycle.Implicit graph mapping array boundary. In LC 287 (Find the Duplicate Number), values are in range
[1, n]while indices are0..n. Index 0 has in-degree 0 (no value is 0), which guarantees that index 0 is never part of the cycle. Starting at index 0 guarantees you traverse the access road into the cycle entrance rather than starting trapped inside the cycle or cycling indefinitely.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Array of n+1 integers in [1, n] + find duplicate + no array modification + O(1) space.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: since values are in [1, n], index 0 is a guaranteed entry root; duplicates have in-degree >= 2, forming a cycle origin.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I treat the array as an implicit functional graph where index i has a directed edge to nums[i]. Since values are in [1, n], 0 is a clean starting node with in-degree 0. The duplicate value has multiple incoming edges, forming the entrance of a directed cycle. I use Floyd's cycle detection to find this entrance in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Phase 1 meets within at most N hops along the implicit functional graph. Phase 2 walks to the cycle entrance in at most N hops. Total operations <= 2N = O(N).
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Uses two integer index variables with zero array mutations.
T(N) = Phase1 + Phase2 = O(N)
Derivation Progression
Traversing indices via nums[i] closes gap by 1 each step inside cycle.
Linear traverse from root 0 and collision index meets at cycle entrance.
O(N) operations
Linear scan without allocating memory or modifying input array.
Variable Definitions
Number of elements (array length is N + 1)
Memory Architecture & Bounds
O(1) Iterative
O(1) Integer pointers only
O(1) Integer duplicate value
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "array of n+1 integers where each integer is in range [1, n]", "only one repeated number", "do not modify the array and use only constant extra space". Implicit functional directed graph: mapping index .
. Must run in time ( optimal) and space without modifying array.
Naive modifications like marking visited indices negative violates the "do not modify array" constraint. Binary search on value range takes ; Floyd's cycle detection achieves optimal time and memory.