Find the Duplicate Number

Learning goal: Recognize why this array problem can be solved as a cycle-detection problem.

Core idea There are n + 1 positions but only n possible values. If each position points to the position named by its value, at least two positions point into the same destination. That collision creates a cycle, and the cycle's entrance identifies the duplicated value.

Algorithm plan

• Start from index 0.
• Interpret nums[index] as the next index.
• Use two pointers moving at different speeds to detect a meeting inside the cycle.
• Restart one pointer at index 0 and move both one step at a time.
• The second meeting point is the cycle entrance and the answer.

Micro-example For nums = [1,3,4,2,2], the links are 0 → 1 → 3 → 2 → 4 → 2. The repeated value 2 causes the cycle 2 → 4 → 2.

Pitfalls

• Do not confuse an index with the value stored at that index.
• The first pointer meeting is not necessarily the duplicate; it is only inside the cycle.
• Sorting and sets solve the problem differently but violate the intended constraints.

Recap

• Values act as next-pointers.
• The duplicate is the cycle entrance.
• Floyd's method uses O(n) time and O(1) space.

Learning goal: Translate the array into a linked list without creating any nodes.

Core idea For every index i, define its successor as next(i) = nums[i]. The array becomes a functional graph: each index has exactly one outgoing edge. Starting at 0, the path must eventually revisit an index because there are finitely many indices. The repeated value is exactly where two incoming paths merge, which becomes the entrance of the resulting cycle.

Data structure model

Micro-example 0 → nums[0] = 1, then 1 → nums[1] = 3, then 3 → nums[3] = 2. Continuing gives 2 → 4 → 2, a cycle whose entrance is 2.

Pitfalls

• The cycle is among indices, even though the returned answer is a value.
• A repeated value means multiple indices can point to the same node.
• No auxiliary linked-list objects are needed.

Recap

• Define next(i) as nums[i].
• Functional graphs eventually cycle.
• The duplicate labels the cycle entrance.

Learning goal: Understand why two pointer walks locate the cycle entrance.

Core idea The first phase uses slow = next(slow) and fast = next(next(fast)). Once both pointers enter the cycle, their relative positions change by one node per iteration, so they must meet. That meeting point gives useful information about the cycle length, but it is not generally the entrance.

Algorithm plan

1. Set slow and fast to index 0.
2. Advance slow one link and fast two links until they meet.
3. Set one pointer back to index 0; keep the other at the meeting point.
4. Advance both one link at a time.
5. Return the index where they meet.

Micro-example In 0 → 1 → 3 → 2 → 4 → 2, the pointers first meet at 4. Resetting one pointer gives 0 → 1 → 3 → 2 and 4 → 2; they meet at 2.

Pitfalls

• Do not return the first meeting point automatically.
• The second phase must move both pointers at the same speed.
• Use while true or an equivalent loop carefully so the initial position is not mistaken for a valid meeting.

Recap

• Phase one finds any point in the cycle.
• Phase two converts that meeting into the entrance.
• Every pointer move is an array read, so the time is linear.

Learning goal: Trace both Floyd phases on one concrete input and connect every move to the array.

Core idea The example has n = 4, so valid values are 1 through 4. Following values from index 0 creates 0 → 1 → 3 → 2 → 4 → 2. The first phase finds an interior meeting, while the reset-and-walk phase identifies the entrance.

Pointer movement

Micro-example Detection: (slow, fast) moves (0,0) → (1,3) → (3,4) → (2,4) → (4,4). Location: reset slow: (0,4) → (1,2) → (3,4) → (2,2); answer 2.

Pitfalls

• In the detection phase, fast reads two links, not two array positions numerically.
• The displayed node is an index; the answer is the same integer used as the duplicate value.
• Keep the exact input unchanged throughout the trace.

Recap

• First meeting: index 4, somewhere inside the cycle.
• Second meeting: index 2, the cycle entrance.
• Return 2.

Learning goal: Distinguish constraint violations from genuine algorithmic errors.

Core idea Several approaches can find a duplicate, but this problem specifically tests whether we can exploit the structure without mutation or linear memory. A set remembers every value, and sorting groups equal values, yet both bypass the intended cycle interpretation. Floyd's algorithm keeps only pointer indices and performs no writes.

Edge-case checklist

• Duplicate near the beginning: The cycle may enter immediately after index 0.
• Duplicate near the end: The tail can be long before the pointers reach the cycle.
• Multiple occurrences: The same repeated integer may appear more than twice; it still labels one cycle entrance.
• Smallest input: With n = 1, [1,1] immediately forms a self-loop at index 1.

Micro-example For [1,1], the links are 0 → 1 → 1. The duplicate is the self-cycle entrance 1.

Pitfalls

• Returning the first Floyd meeting instead of running phase two.
• Treating nums[i] as data only rather than as a next index.
• Accidentally writing into nums while trying to mark visited values.

Recap

• Preserve the input.
• Use no visited set.
• Always complete both pointer phases.

Learning goal: State the final algorithm, proof idea, and complexity precisely.

Core idea The array induces a linked-list-like walk with one outgoing link per index. Because a duplicate value creates a shared destination, the walk contains a cycle. Floyd's first phase proves and locates a cycle intersection; the second phase identifies its entrance, which is the duplicate.

Algorithm plan

slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
    slow = nums[slow]
    fast = nums[nums[fast]]

slow = 0
while slow != fast:
    slow = nums[slow]
    fast = nums[fast]
return slow

Micro-example For [1,3,4,2,2], the pointers meet first at 4, then meet again at 2 after resetting slow.

Pitfalls

• Time is O(n), not O(n²): each phase traverses only a constant number of paths.
• Space is O(1): only pointer variables are added.
• The array remains unchanged from input to return.

Recap

• Model nums[i] as next(i).
• Detect a cycle, then locate its entrance.
• Return the entrance in O(n) time and O(1) space.