Problem

Given an integer array nums containing n + 1 integers, where:

  • Every number is in the range [1, n].
  • There is exactly one duplicate number.
  • The duplicate may appear more than twice.

Return the duplicate number.

Example

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

Follow-up

Can you solve it:

  • Without modifying the array?
  • Using only O(1) extra space?

Key Observation

At first glance, this looks like a hashing problem.

A straightforward solution would be:

  • Use a set
  • Traverse the array
  • Return the first number already seen

Time Complexity:

  • O(n)

Space Complexity:

  • O(n)

However, the follow-up explicitly asks for O(1) extra space, so we need a different approach.

The Hidden Graph

The trick is to stop thinking of the array as just numbers.

Instead, think of every index as a node.

Each value tells you where to go next.

index: 0 1 2 3 4

nums : 1 2 3 2 2

This becomes

0 → 1
1 → 2
2 → 3
3 → 2
4 → 2

Starting from index 0:

0 → 1 → 2 → 3
         ↑   ↓
         └───┘

Notice something?

There’s a cycle.

Why?

Because one value appears twice.

Two different indices point to the same next node.

Since every value is between 1 and n, every node has exactly one outgoing edge. With n + 1 nodes pointing into only npossible values, a cycle is guaranteed by the pigeonhole principle.

Even better:

The entrance of this cycle is exactly the duplicate number.

So now the problem becomes:

Find the entrance of a cycle in a linked list.

That’s exactly what Floyd’s Tortoise and Hare Algorithm does.

Step 1: Detect the Cycle

We use two pointers:

  • slow moves one step.
  • fast moves two steps.
slow = fast = 0

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

    if slow == fast:
        break

Eventually, both pointers meet inside the cycle.

For example:

0 → 1 → 2 → 3
         ↑   ↓
         └───┘

slow: 0 → 1 → 2 → 3
fast: 0 → 2 → 2 → 2

After enough steps, they collide.

Step 2: Find the Cycle Entrance

Once they meet, reset another pointer to the beginning.

slow2 = 0

while True:
    if slow == slow2:
        return slow

    slow = nums[slow]
    slow2 = nums[slow2]

Now both pointers move one step at a time.

They will meet at the entrance of the cycle, which is exactly the duplicate number.

Why Does This Work?

Suppose:

  • Distance from the start to the cycle entrance = L
  • Distance from the entrance to the meeting point = X
  • Cycle length = C

When the two pointers meet:

Fast distance = 2 × Slow distance

Using Floyd’s proof, it follows that if one pointer starts from the beginning and the other starts from the meeting point, moving both one step at a time, they’ll meet at the cycle entrance.

Since the cycle entrance corresponds to the repeated value, that’s our answer.

Dry Run

Input:

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

Graph:

0 → 1 → 3 → 2 → 4
          ↑     ↓
          └─────┘

Phase 1

slow = 0
fast = 0

slow = 1
fast = 3

slow = 3
fast = 4

slow = 2
fast = 4

slow = 4
fast = 4

Pointers meet at node 4.

Phase 2

slow = 4
slow2 = 0

slow -> 2
slow2 -> 1

slow -> 4
slow2 -> 3

slow -> 2
slow2 -> 2

They meet at 2.

Duplicate number = 2.

Solution

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0

        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        slow2 = 0

        while True:
            if slow == slow2:
                return slow

            slow = nums[slow]
            slow2 = nums[slow2]

Complexity Analysis

  • Time Complexity: O(n)
    • Cycle detection takes at most O(n).
    • Finding the cycle entrance also takes at most O(n).
  • Space Complexity: O(1)Only a few pointers are used.

Key Takeaways

  • Don’t think of the array as just values—treat it as a graph where each value is the next pointer.
  • The duplicate creates a cycle because two indices eventually lead to the same node.
  • Floyd’s Tortoise and Hare algorithm detects that cycle without modifying the array.
  • Resetting one pointer to the start lets you find the cycle entrance, which is the duplicate number.
  • This elegant approach satisfies both follow-up constraints: O(n) time and O(1) extra space.