Find the Duplicate Number

Find the duplicate number in an array of n + 1 integers.

ArrayTwo Pointers

Pattern fit

The array can be reinterpreted as a linked structure where value points to next index, making the duplicate the cycle entry and turning the problem into Floyd cycle detection.

Key observation

You are not searching values directly; you are detecting a cycle in an implicit graph.

Target complexity

O(n) / O(1)

How to break down the solution cleanly

The array can be reinterpreted as a linked structure where value points to next index, making the duplicate the cycle entry and turning the problem into Floyd cycle detection.

You are not searching values directly; you are detecting a cycle in an implicit graph.

Write down what each pointer means before you move them.

Use the current comparison to prove which side can be safely discarded.

Reference implementation

Python

# Generic pattern template
# Opposite-direction pointers on a sorted array
left, right = 0, len(nums) - 1
while left < right:
    if good(nums[left], nums[right]):
        return answer
    if should_move_left(nums[left], nums[right]):
        left += 1
    else:
        right -= 1

# Fast/slow pointers
slow = 0
for fast in range(len(nums)):
    if keep(nums[fast]):
        nums[slow] = nums[fast]
        slow += 1

Common pitfalls

warning

Thinking the two pointers move over indices in the normal array sense.

warning

Forgetting the second phase needed to find the cycle entry.

Common follow-ups

Why does the cycle entry equal the duplicate value?

What alternative counting or binary-search methods exist?

Continue with related problems

Build repeatable depth inside the Two Pointers cluster before moving on.

view_weekBack to the pattern page

#11

Container With Most Water

Pick two lines that form the container with maximum area.

#31

Next Permutation

Transform the array into the next lexicographically larger permutation.

#33

Search in Rotated Sorted Array

Search for a target in a rotated sorted array.