LeetCode #287 Medium

Find the Duplicate Number

An array of n + 1 integers holds values in [1, n]. One value repeats. Find it without modifying the array and in O(1) space.

arraytwo-pointersfloyd

Open on LeetCode ↗

02

Intuition

Read each index as a pointer i → nums[i]. Because two indices share a value, this functional graph contains a cycle, and the duplicate is the cycle's entrance. Floyd's tortoise and hare finds that entrance without extra space.

How to spot this pattern

Treat the array as a function i → nums[i] and it becomes a linked list where the duplicate value is the node two pointers enter from different places — that is, the cycle entrance. Floyd's algorithm then applies unchanged. The constraint "don't modify the array, use O(1) space" is the tell that a cycle reading is intended.

03

Approach

1

The easy solutions each break a rule

A hash set finds the repeat instantly but uses O(n) space; sorting finds it but mutates the array. The problem forbids both. To respect 'read-only and O(1) space' we need to see hidden structure in the input — and there's a beautiful one: the values themselves can be read as pointers.

2

Read the array as a linked list with a cycle

Interpret each index as a pointer: i leads to nums[i]. Because there are n+1 slots but values only range over [1, n], two different indices must point to the same place — and that collision means following the pointers eventually revisits a node, i.e. forms a cycle. Crucially, the entrance of that cycle is exactly the duplicated value, because that's the value two indices point into.

3

Floyd's two-phase cycle finding

Now it's the classic 'find the start of a cycle' problem. Phase 1: move slow one hop and fast two hops until they meet somewhere inside the loop (a fast pointer must lap a slow one in a cycle). Phase 2: reset slow to the start and advance both one hop at a time; the distance arithmetic of Floyd's algorithm guarantees they collide precisely at the cycle's entrance — the duplicate. Only index reads, two variables: O(n) time, O(1) space, array untouched.

04

Solution & live demo

▶1class Solution:
▶2    def findDuplicate(self, nums):
▶3        slow = fast = nums[0]
▶4        while True:
▶5            slow = nums[slow]
▶6            fast = nums[nums[fast]]
▶7            if slow == fast:
▶8                break
▶9        slow = nums[0]
▶10        while slow != fast:
▶11            slow = nums[slow]
▶12            fast = nums[fast]
▶13        return slow

05

Common pitfalls

Returning the meeting point

✗ Wrong

if slow == fast:
    return slow

✓ Right

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

The meeting point is somewhere inside the cycle, not necessarily its entrance. The second phase — restarting one pointer at the head and stepping both one at a time — is what converges on the entrance, which is the duplicate.

Moving both pointers at the same speed in phase two

✗ Wrong

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

✓ Right

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

Phase one needs the 2:1 speed ratio to guarantee a meeting; phase two needs them equal so the distance argument places them at the entrance together. Keeping the fast pointer doubled makes them meet at the wrong node or skip past each other.

Sorting or marking visited entries

✗ Wrong

for n in nums:
    if nums[abs(n)] < 0: return abs(n)
    nums[abs(n)] *= -1

✓ Right

slow = fast = nums[0]

Negation-marking works but mutates the input, which the problem forbids; sorting mutates it too and costs O(n log n). Floyd's runs in O(n) time and O(1) space while leaving the array untouched.

06

Edge cases

Duplicate appears many times, e.g. [2,2,2,2,2]

Floyd's method finds the cycle entrance regardless of how many times the value repeats.

Duplicate at the array's edges

Indexing by value, not position, makes the location in the array irrelevant to the cycle math.

Read-only requirement

Only index reads are used; the array is never written, satisfying the no-modify rule.

07

Complexity

Time

O(n)

Space

O(1)

Two phases, each linear; only two index variables.