Find the Duplicate Number | Leetcode 287

Welcome to our deep dive on Find the Duplicate Number (Leetcode 287). This problem has notoriously strict constraints, forcing us to abandon standard sets or sorting methods, leading to an incredibly clever application of Linked List cycle detection on a standard Array!

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example: nums = [1,3,4,2,2] => Output: 2

The Trap: Standard Approaches

Usually, finding a duplicate is trivial:

1. HashSet / Visited Array: Store every element seen so far. If you see it again, that's your duplicate.
   • Problem: Requires O(N) space. The problem demands O(1) space!
2. Sorting: Sort the array and linearly scan for adjacent identical numbers.
   • Problem: Sorting explicitly modifies the array. The problem states we cannot modify nums.

Because of these constraints, we must map this array to a Linked List format mentally.

Approach: Floyd's Tortoise and Hare O(N)

Since the array numbers are strictly in the range [1, n] and there are n + 1 elements, we can treat the array values as pointers to the next index.

For instance, in nums = [1,3,4,2,2]:

• Index 0 points to value 1.
• Index 1 points to value 3.
• Index 3 points to value 2.
• Index 2 points to value 4.
• Index 4 points to value 2 (Cycle!)

Because multiple indices will point purely at the identical duplicated value, this implicitly forms a cycle. Specifically, the Duplicate Number inherently is the entrance to the cycle! We just use Floyd's algorithm.

1. Phase 1: Detect Intersection: Start a slow pointer moving 1 step at a time, and a fast pointer moving 2 steps. Since there's a duplicate, a cycle is mathematically guaranteed. They will intersect.
2. Phase 2: Find the Cycle Entrance: Reset the slow pointer back to 0. Keep the fast pointer at the intersection point. Now, move both pointers 1 step at a time. The exact node where they collide again is structurally guaranteed to be the start of the cycle (the duplicate number).

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = 0
        fast = 0
        
        # Phase 1: Hunt for the intersection point in the cycle
        while True:
            slow = nums[slow]           # 1 step
            fast = nums[nums[fast]]     # 2 steps
            
            if slow == fast:
                break
                
        # Phase 2: Find the entrance to the cycle (the duplicate)
        slow2 = 0
        while True:
            slow = nums[slow]           # 1 step
            slow2 = nums[slow2]         # 1 step
            
            if slow == slow2:
                return slow

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (287)