287. Find the Duplicate Number

At a Glance

• Topic: linked-list
• Pattern: Fast & Slow Pointers (Floyd on implicit graph)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Apple, Bloomberg
• Frequency: Very High
• LeetCode: 287

Problem (one-liner)

Given nums of length n+1 containing integers in [1..n] with exactly one repeated value, return that duplicate. Must use O(1) extra space and must not modify the array (for the strict follow-up).

Recognition Cues

• Pigeonhole → duplicate exists
• O(1) space bar on array problems often means “treat indices as graph”
• index -> nums[index] form functional graph with a cycle; duplicate is cycle entry

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n²) — compare all pairs.
• Better — O(n) time / O(n) space — hash set or sort copy (if sorting allowed).
• Optimal — O(n) time / O(1) space — Floyd’s tortoise and hare on index jumps; same phase-two entry trick as linked list cycle II.

Optimal Solution

Go

func findDuplicate(nums []int) int {
	slow := 0
	fast := 0
	for {
		slow = nums[slow]
		fast = nums[nums[fast]]
		if slow == fast {
			break
		}
	}
	slow = 0
	for slow != fast {
		slow = nums[slow]
		fast = nums[fast]
	}
	return slow
}

JavaScript

function findDuplicate(nums) {
	let slow = 0;
	let fast = 0;
	while (true) {
		slow = nums[slow];
		fast = nums[nums[fast]];
		if (slow === fast) {
			break;
		}
	}
	slow = 0;
	while (slow !== fast) {
		slow = nums[slow];
		fast = nums[fast];
	}
	return slow;
}

Walkthrough

nums = [1,3,4,2,2] — edges 0->1->3->2->4->2 creates cycle through duplicate 2.

Edge Cases

• Minimal length where duplicate appears twice early.
• Duplicate not at index matching its value — graph still well-defined.

Pitfalls

• Confusing with “swap to correct index” solutions — those mutate input.
• Using Floyd on values instead of indices — must start from index 0 as graph root.

Similar Problems

• 142. Linked List Cycle II — identical second phase.
• 141. Linked List Cycle — detection intuition.
• 202. Happy Number — cycle detection on iterated function.

Variants

• Multiple duplicates — problem changes; frequency map or modified approaches.
• Binary search on answer value — alternative O(n log n) without Floyd.

Mind-Map Tags

#floyd #index-graph #pigeonhole #cycle-entry