Find the Duplicate Number Solution

Problem

You are given an array of n + 1 integers where every value lies in the range [1, n]. Exactly one number appears more than once — find it. The goal is to do this without modifying the array and without allocating more than a constant amount of extra memory.

Input: nums = [1, 3, 4, 2, 2]
Output: 2
Explanation: 2 appears at indices 3 and 4; every other value appears exactly once.

A counter-example shows why the constraint matters: [3, 1, 3, 4, 2] also has duplicate 3 — a sort would find it in O(n log n) and a hash set in O(n) space, but neither approach satisfies both constraints simultaneously.

Intuition

Think of each element nums[i] as a pointer: standing at index i, you jump to index nums[i]. Because values are in [1, n], you can never jump to index 0 — so the sequence always begins at index 0 and proceeds inward. The duplicate value means two different indices point to the same next index, which creates exactly one cycle. Finding the cycle's entry point using Floyd's algorithm gives the duplicate in linear time with no extra space.

Approach 1 — Hash Set

Walk through the array and record every value in a set. The first value already in the set when you try to insert it is the duplicate.

Initialize an empty set.
Iterate through each value in nums.
If the value is already in the set, return it immediately.
Otherwise, add it to the set and continue.

1from typing import List
2
3def findDuplicate(nums: List[int]) -> int:
4    seen = set()
5    for num in nums:
6        if num in seen:
7            return num
8        seen.add(num)
9    return -1  # unreachable: problem guarantees a duplicate exists

Time: O(n) — each element is inserted or looked up once.
Space: O(n) — the set holds up to n distinct values before finding the duplicate.

Approach 2 — Floyd's Cycle Detection

Model the array as an implicit linked list: index i has a "next" pointer to index nums[i]. Because two indices share the same value (the duplicate), two arrows point to the same destination — that creates a cycle, and the duplicate is where the cycle begins. Floyd's tortoise-and-hare algorithm finds the cycle entry in two phases without any extra storage.

Initialize slow = nums[0] and fast = nums[nums[0]] — fast takes two steps where slow takes one.
Advance both until they meet inside the cycle (this is guaranteed to happen).
Reset a second slow pointer slow2 to index 0; keep the first slow at the meeting point.
Advance both one step at a time until they meet — the meeting point is the cycle entry, which equals the duplicate.
Return that value.

1from typing import List
2
3def findDuplicate(nums: List[int]) -> int:
4    # Phase 1: find where the two pointers meet inside the cycle
5    slow = nums[0]
6    fast = nums[nums[0]]  # fast starts two hops ahead so the loop condition works immediately
7    while slow != fast:
8        slow = nums[slow]
9        fast = nums[nums[fast]]  # fast always advances two indices per step
10
11    # Phase 2: locate the cycle entry (the duplicate value)
12    slow2 = 0  # restart one pointer from the sequence origin
13    while slow2 != slow:
14        slow2 = nums[slow2]
15        slow = nums[slow]
16
17    return slow

Time: O(n) — both phases traverse the implicit list at most a constant number of full loops.
Space: O(1) — only two integer pointers are needed regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Hash Set	O(n)	O(n)	When the interviewer hasn't added the O(1) space constraint
Floyd's Cycle Detection	O(n)	O(1)	When both O(1) space and no array modification are required

Common Mistakes

Starting both pointers at nums[0]: If slow and fast begin at the same position, the while slow != fast loop exits immediately and returns the wrong answer. Fast must begin two steps ahead — at nums[nums[0]] — so the loop body runs at least once.
Returning the result after phase 1 without running phase 2: The meeting point in phase 1 is somewhere inside the cycle, not at the cycle entry. The actual duplicate is only found after phase 2 converges both pointers to the entry.
Restarting phase 2 from index 1 instead of 0: Values start at 1, but the implicit linked list is entered from index 0. Starting slow2 at 1 assumes the list begins at value 1, which skips the true head and gives the wrong cycle entry.
Negating nums[nums[i]] to mark visited indices: A common alternative approach flips the sign of the value at position nums[i], but this modifies the array, which the full constraints forbid — and it's easy to confuse which index is being marked.
Thinking the hare might "lap" the tortoise and never meet: In a finite cycle, if the hare is behind the tortoise by k steps, each iteration reduces that gap by 1. They always converge; the hare cannot skip over a single-node gap.

Find the Duplicate Number — Solution