287. Find the Duplicate Number

Problem¶

Given n + 1 integers in the range \([1,n]\), return the only distinct value that occurs more than once. Do not modify the array, and use \(O(1)\) extra space.

nums = [1, 3, 4, 2, 2] -> duplicate = 2

A duplicate must exist by the pigeonhole principle: n + 1 values occupy only n possible values.

Key trick¶

Treat each value as a pointer to another array index. The duplicate becomes the entrance of a cycle, so Floyd's tortoise-and-hare algorithm finds it in linear time and constant space.

Trap¶

• The first intersection of the slow and fast pointers is not necessarily the cycle entrance.
• XOR and sum formulas fail when the duplicate appears more than twice and some values are absent.
• Sorting modifies the array, while a set requires \(O(n)\) extra space.

Why is it interesting?¶

It transforms an array duplicate problem into linked-list cycle detection without changing the input.

Python solution¶

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # Values act as next pointers, forming a path that enters a cycle.
        slow = fast = nums[0]

        # Find an intersection inside the cycle.
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Starting one pointer at the path's beginning makes their next
        # intersection the cycle entrance, which is the duplicate value.
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

Time complexity: \(O(n)\)

Space complexity: \(O(1)\)

Comment on my solution¶

• The XOR approach assumes each non-duplicate value appears once and the duplicate appears exactly twice.
• The actual constraints allow the duplicate to occur more than twice, leaving some values absent.

nums = [3, 3, 3, 3, 3]
XOR(nums) XOR XOR(1..4) = 7, not 3

• The method also has no return statement.
• The constant-space observation was good, but multiplicity makes arithmetic cancellation unreliable.

# Ideas:
# - the constant space constraint
#   - maybe use math formula
#   - or bit operation
#   - it reminds of unique integer in array which can be solved by
#     XORing all intergers
#     - XOR can work also here
#     - a ^ a = 0
# - [1,3,4,2,2] -> 2
#   n1 + n2 + n3 + x + x

# WRONG
class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # [1,3,4,2,2] -> 2
        # [3,3,3,3,3] -> 3
        acc = 0
        for x in nums:
            acc ^= x
        for x in range(1, len(nums)):
            acc ^= x # cancel x

Extra¶

Example of first intersection not being the cycle entrance¶

Give me an example of an array such that the first intersection inside the cycle, and so is different from the cycle entrance which is if I understand correctly the duplicate number.

Consider:

nums = [1, 2, 3, 4, 2]

Each index points to the index given by its value:

0 -> 1 -> 2 -> 3 -> 4
          ^         |
          |_________|

The cycle is:

2 -> 3 -> 4 -> 2

The cycle entrance is 2, which is also the duplicate because two indices point to it:

nums[1] = 2
nums[4] = 2

Starting with both pointers at nums[0], which is 1:

Their first intersection is 4, not the cycle entrance 2.

Now reset slow to nums[0] while leaving fast at the intersection:

They meet at 2, the cycle entrance and duplicate.

The first phase only guarantees an intersection somewhere inside the cycle. The second phase locates the entrance.

Why the Floyd's tortoise-and-hare algo finds the cycle entrance¶

But why does the algorithm even work at all?

1. Why is there a cycle?¶

The algorithm works because the array can be interpreted as a linked structure.

Define the next node as:

next_node = nums[current_node]

Every value is in \([1,n]\), so following pointers always stays within indices \(1\) through \(n\). Because there are finitely many indices, eventually an index must repeat. Repeating an index creates a cycle.

The cycle entrance is the duplicate value: at least two different indices point to that value. Since the problem guarantees only one distinct duplicate, that collision must occur at the duplicate.

2. Why do slow and fast meet?¶

Let:

• \(\mu\) be the distance from the starting node to the cycle entrance.
• \(\lambda\) be the cycle length.
• \(t\) be the number of steps taken by the slow pointer.

At that time:

• Slow has moved \(t\) steps.
• Fast has moved \(2t\) steps.

When they meet, fast has traveled \(t\) more steps than slow. Inside a cycle, they can occupy the same node only when that difference is a multiple of the cycle length:

Intuitively, fast eventually laps slow because it gains one cycle position per iteration.

3. Why does resetting one pointer find the entrance?¶

Slow traveled \(\mu\) steps before entering the cycle. Therefore, its position at the meeting point is:

Because \(t\) is a multiple of \(\lambda\):

So the meeting point is exactly \(\mu\) steps before the cycle entrance, counting around the cycle.

Now:

• Reset one pointer to the beginning.
• Leave the other at the meeting point.
• Move both one step at a time.

After \(\mu\) steps:

• The reset pointer has reached the cycle entrance.
• The other pointer has moved \(\mu\) positions around the cycle and also reached the entrance.

Therefore, their next meeting is the cycle entrance, which is the duplicate number.

For your example:

1 -> 2 -> 3 -> 4 -> 2

• \(\mu = 1\)
• \(\lambda = 3\)
• First meeting is at 4
• Moving one step from both 1 and 4 reaches 2
• 2 is the cycle entrance and duplicate