LeetCode · #287

Find the Duplicate Number Solution

Given an array of n+1 integers in range [1, n], find the one repeated number — without modifying the array and in O(1) extra space.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #287

🏗️

Pattern

Floyd's Cycle Detection — index as linked list

Given an array nums containing n+1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number. Find and return it. You must not modify the array and must use only O(1) extra space.

Example

 Input: nums = [1,3,4,2,2]
Output: 2 

Constraints

 • 1 ≤ n ≤ 10⁵ • nums.length == n + 1 • 1 ≤ nums[i] ≤ n • Exactly one number repeats (possibly more than once) 

Section Two · Approach 1

HashSet — O(n) space

Traverse the array, adding each value to a set. If a value is already in the set, it's the duplicate. O(n) time but O(n) space — violates the constraint.

Problem: O(n) extra space. Sorting modifies the array. The key insight: treat the array as a linked list where index i points to nums[i]. The duplicate creates a cycle — use Floyd's algorithm.

Section Three · Approach 2

Floyd's Cycle Detection — O(n) time, O(1) space

Treat the array as a function: f(i) = nums[i]. Starting from index 0, follow next = nums[current]. Since n+1 values map to n positions, by pigeonhole there's a cycle — and the cycle's entry point is the duplicate value.

💡 Mental model: Imagine each array index is a room, and the value at that index tells you which room to go to next. Two rooms have the same destination (the duplicate value). This creates a loop — like a hallway that leads back to an earlier room. Floyd's algorithm finds where the loop begins.

Algorithm

Phase 1 — Detect cycle: slow = nums[0], fast = nums[0]. Move slow by 1 hop, fast by 2. They meet inside the cycle.
Phase 2 — Find entry: Reset slow to nums[0]. Move both by 1 hop. They meet at the cycle entry = the duplicate.

🎯 Why this works:

Start from index 0 (which is safe — no value points to 0 since values are in [1,n]).
The duplicate value X means two indices point to X, so X has two "incoming edges" — creating a cycle entry.
Floyd's phase 2 finds exactly this entry point.

Section Four · Trace

Visual Walkthrough

Trace: nums = [1, 3, 4, 2, 2]. Index chain: 0→1→3→2→4→2→4→... (cycle at 2).

Floyd's on index-value "linked list"

Section Five · Implementation

Code — Java & Python

Java — Floyd's Cycle Detection

 class Solution {
public int findDuplicate(int[] nums) {
// Phase 1: Find meeting point int slow = nums[0], fast = nums[0];
do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
// Phase 2: Find cycle entry
slow = nums[0];
while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
return slow;
    }
}

Python — Floyd's Cycle Detection

 class Solution:
def findDuplicate(self, nums: list[int]) -> int:
# Phase 1: Find meeting point
slow = fast = nums[0]
while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
if slow == fast: break # Phase 2: Find cycle entry
slow = nums[0]
while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
return slow

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
HashSet	O(n)	O(n)	Violates space constraint
Sort	O(n log n)	O(1)*	Modifies array (*in-place sort)
Floyd's ← optimal	O(n)	O(1)	No modification, constant space

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Duplicate at start	`[2, 2, 1]`	Fast cycle entry detected quickly.
Many duplicates	`[2, 2, 2, 2]`	Duplicate appears n times. Floyd still finds 2.
Minimum	`[1, 1]`	n=1, chain: 0→1→1→1... cycle at 1.

⚠ Common Mistake: Starting both pointers from index 0 instead of nums[0] — or starting from nums[0] in phase 2 and index 0 in phase 1. Phase 1: both start at nums[0]. Phase 2: one resets to nums[0] (not 0), the other stays at the meeting point. Consistency matters.

← Back to Linked List problems

LearningTree

LC 287 · Find the Duplicate Number — Solution & Explanation | DSA Guide