Find the Duplicate Number

LeetCode 287: Find the Duplicate Number Solution & Explanation

Problem Overview

TL;DR: By treating the array indices and values as nodes and pointers in a linked list, we use Floyd's Cycle Detection (Fast & Slow Pointers) to identify the duplicate number in linear time and constant space.

The LeetCode 287 problem, titled "Find the Duplicate Number," presents an array of integers nums containing n + 1 integers. Each integer falls within the range [1, n]. The problem guarantees that exactly one number is repeated (though it may appear more than twice). The objective is to identify this duplicate number.

Crucially, the solution must adhere to strict constraints:

1. Do not modify the original array (e.g., no sorting).
2. Use only constant $O(1)$ extra space (e.g., no hash sets).
3. Solve it in less than $O(n^2)$ time complexity.

Brute Force Approach for Find the Duplicate Number

The most intuitive way to solve this without extra space is to compare every number with every other number to check for duplicates. We can iterate through the array with two nested loops.

Pseudo-code:

for i from 0 to n:
    for j from i + 1 to n:
        if nums[i] == nums[j]:
            return nums[i]

Time Complexity Analysis: The time complexity is $O(n^2)$ because for an array of size $N$, we perform roughly $N^2/2$ comparisons.

Why it fails: While this approach satisfies the space constraint and the "no modification" constraint, it fails on time efficiency. For large inputs ($N = 10^5$), $N^2$ operations result in $10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed by online judges, leading to a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Two Pointer Patterns

We utilize the Fast & Slow pointer strategy to separate the process into two phases:

1. Intersection Phase:

   • Initialize two pointers, slow and fast, both starting at the head (index 0).
   • Move slow one step at a time: slow = nums[slow].
   • Move fast two steps at a time: fast = nums[nums[fast]].
   • Continue until slow and fast collide. They are guaranteed to meet inside the cycle.

2. Entrance Finding Phase:

   • The meeting point is not necessarily the duplicate number; it is just some node within the cycle.
   • To find the entrance (the duplicate), keep one pointer at the meeting point and reset the other pointer to the start (index 0).
   • Move both pointers one step at a time.
   • The point where they collide is the cycle entrance (the duplicate number).

This strategy maintains constant space because we only store two integer variables (the pointers), and it does not modify the array.

Execution Flow

1. Initialization:

   • Set slow = nums[0].
   • Set fast = nums[0].

2. Phase 1: Detect Cycle:

   • Enter a loop.
   • Update slow to nums[slow].
   • Update fast to nums[nums[fast]].
   • Check if slow == fast. If they are equal, a cycle is detected. Break the loop.

3. Phase 2: Find Duplicate:

   • Reset slow to nums[0] (restarting from the head).
   • Keep fast at the collision index.
   • Enter a second loop.
   • Check if slow == fast. If yes, we have found the duplicate.
   • If no, advance both pointers by one step: slow = nums[slow], fast = nums[fast].
   • Repeat until they match.

4. Result:

   • Return the value of slow (or fast) as the duplicate number.

Proof of Correctness

Let $L$ be the distance from the head (index 0) to the cycle entrance. Let $C$ be the length of the cycle. Let $X$ be the distance from the cycle entrance to the meeting point of the fast and slow pointers.

When the pointers meet:

• The slow pointer has traveled distance $D_s = L + X$.
• The fast pointer has traveled distance $D_f = L + X + nC$ (it has looped around the cycle $n$ times).
• Since the fast pointer moves at $2\times$ speed, $D_f = 2 \times D_s$.

Substituting the distances: $2(L + X) = L + X + nC$ $2L + 2X = L + X + nC$ $L + X = nC$ $L = nC - X$

The equation $L = nC - X$ implies that the distance from the head to the cycle entrance ($L$) is exactly equal to the distance from the meeting point to the cycle entrance ($nC - X$) if we wrap around the cycle. Therefore, moving one pointer from the head and one from the meeting point at the same speed ensures they will meet precisely at the cycle entrance.

Pattern Reuse Notes

The Two Pointers - Fast & Slow pattern is a powerful tool for cycle detection and list traversal.

• LeetCode 141: Linked List Cycle: Uses the exact same intersection logic (Phase 1) to determine if a linked list contains a cycle.
• LeetCode 202: Happy Number: Generates a sequence of numbers (sum of squared digits). Fast & Slow pointers are used to detect if the sequence loops endlessly or reaches 1.
• LeetCode 392: Is Subsequence: While primarily a standard Two Pointer problem (one for each string), it shares the fundamental concept of traversing data structures with pointers moving at different rates or conditions.

Understanding LeetCode 287 solidifies your grasp of Floyd's Cycle Detection, making these related problems significantly easier to solve.

Reference Implementation

C++ Solution for LeetCode 287

1class Solution {
2public:
3    int findDuplicate(vector<int>& nums) {
4        // Initialize pointers based on the first element
5        int slow = nums[0];
6        int fast = nums[0];
7
8        // Phase 1: Find the intersection point of the two runners.
9        do {
10            slow = nums[slow];           // Move slow pointer 1 step
11            fast = nums[nums[fast]];     // Move fast pointer 2 steps
12        } while (slow != fast);
13
14        // Phase 2: Find the "entrance" to the cycle.
15        slow = nums[0];                  // Reset slow to start
16        while (slow != fast) {
17            slow = nums[slow];           // Move both 1 step
18            fast = nums[fast];
19        }
20
21        return slow;
22    }
23};

Java Solution for LeetCode 287

1class Solution {
2    public int findDuplicate(int[] nums) {
3        // Initialize pointers
4        int slow = nums[0];
5        int fast = nums[0];
6
7        // Phase 1: Detect cycle intersection
8        do {
9            slow = nums[slow];           // Move slow pointer 1 step
10            fast = nums[nums[fast]];     // Move fast pointer 2 steps
11        } while (slow != fast);
12
13        // Phase 2: Find the entrance to the cycle
14        slow = nums[0];                  // Reset slow to head
15        while (slow != fast) {
16            slow = nums[slow];           // Move both 1 step
17            fast = nums[fast];
18        }
19
20        return slow;
21    }
22}

Python Solution for LeetCode 287

1class Solution:
2    def findDuplicate(self, nums: List[int]) -> int:
3        # Phase 1: Detect cycle intersection
4        slow = nums[0]
5        fast = nums[0]
6        
7        while True:
8            slow = nums[slow]           # Move slow pointer 1 step
9            fast = nums[nums[fast]]     # Move fast pointer 2 steps
10            if slow == fast:
11                break
12        
13        # Phase 2: Find the entrance to the cycle
14        slow = nums[0]                  # Reset slow to head
15        while slow != fast:
16            slow = nums[slow]           # Move both 1 step
17            fast = nums[fast]
18            
19        return slow