Find the Duplicate Number

How it works

Treat the array like a linked list, where each index points to the next index given by its value.
Because one number is duplicated, two indices will point into the same chain, creating a cycle — exactly like a linked list with a loop.

Using Floyd’s Fast & Slow Pointer technique:

1. The slow pointer moves one step at a time.
2. The fast pointer moves two steps at a time.
3. If there’s a cycle, they will eventually meet.

Once they meet, we start a new pointer from the beginning:

• Move both pointers one step at a time.
• The point where they meet again is the duplicate number (the entry point of the cycle).

Steps

1. Initialize two pointers slow = 0 and fast = 0.
2. Move:
   • slow = nums[slow]
   • fast = nums[nums[fast]] until slow == fast.
3. Start a new pointer slow2 = 0.
4. Move both:
   • slow = nums[slow]
   • slow2 = nums[slow2] until they meet.
5. The meeting point is the duplicate number.
6. Return that number.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Modifying the Array When Not Allowed

Some problem variants require not modifying the input array. Solutions like negative marking or in-place sorting alter the original data. Always check the constraints before choosing an approach that mutates the input.

Off-by-One Errors in Index Mapping

Since values range from 1 to n but array indices start at 0, forgetting to subtract 1 when mapping values to indices causes out-of-bounds errors or incorrect results. For example, value n maps to index n-1, not index n.

Misunderstanding Floyd's Cycle Detection Entry Point

In the fast and slow pointer approach, the meeting point of the two pointers is not the duplicate number. After they meet, you must start a new pointer from index 0 and move both pointers one step at a time until they meet again. This second meeting point is the cycle entry, which corresponds to the duplicate value.

from typing import List

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

        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                break;
            }
        }

        int slow2 = 0;
        while (true) {
            slow = nums[slow];
            slow2 = nums[slow2];
            if (slow == slow2) {
                return slow;
            }
        }
    }
};