NUHMAN.com

Introduction

LeetCode 287: Find the Duplicate Number is a problem where you are given an array of integers. Each integer is between 1 and n, where n is the size of the array. The array contains n + 1 integers, meaning that there is one duplicate number in the array. Your task is to find that duplicate number without modifying the array, and using O(1) space.

This is an interesting problem that can be solved efficiently using a variety of techniques, including Floyd’s Tortoise and Hare (Cycle Detection) and Binary Search.

Problem Statement

Given an integer array nums of length n + 1 where each integer is between 1 and n (inclusive), there is only one duplicate number in the array. You need to find that duplicate number.

Note:

• You cannot modify the array (i.e., you cannot sort it).
• You must solve it using O(1) space and O(n) time complexity.

Example

python

Input: [1, 3, 4, 2, 2]

Output: 2

Explanation: The duplicate number is 2.

✅ Step-by-Step Solution

🧠 Intuition

This problem can be viewed as a cycle detection problem in a linked list:

• The elements of the array can be seen as a linked list where each number points to another number in the array.
• The duplicate number will cause a cycle in this "linked list" since the same number will be "visited" twice.

We can solve this problem using Floyd’s Tortoise and Hare Algorithm (Cycle Detection), which is a fast and slow pointer approach.

✅ Approach

Using Floyd’s Tortoise and Hare Algorithm (Cycle Detection)

1. Initial Setup: Consider the array as a linked list where each value points to the index of the next value. For example, nums[i] will point to the value at index nums[i].
2. Two Pointers:

• Tortoise (slow pointer): Moves one step at a time (nums[tortoise]).
• Hare (fast pointer): Moves two steps at a time (nums[hare]).

1. Cycle Detection:

• The two pointers will eventually meet inside a cycle because of the duplicate number.

1. Find the Entrance to the Cycle:

• Once the pointers meet, reset one pointer to the start and leave the other where they met.
• Move both pointers one step at a time. The point where they meet again is the duplicate number.

✅ Python Code

python

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        # Phase 1: Find the intersection point inside the cycle
        tortoise = nums[0]
        hare = nums[0]
        
        # Start moving tortoise and hare at different speeds
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        
        # Phase 2: Find the entrance to the cycle (duplicate number)
        tortoise = nums[0]
        while tortoise != hare:
            tortoise = nums[tortoise]
            hare = nums[hare]
        
        return hare

🧪 How It Works

1. Phase 1: Cycle Detection

• Start both tortoise and hare at the first element (nums[0]).
• Move tortoise one step at a time, and hare two steps at a time.
• When tortoise and hare meet, we know there is a cycle caused by the duplicate.

1. Phase 2: Finding the Entrance to the Cycle

• Reset tortoise to the start of the array, but keep hare at the meeting point.
• Move both pointers one step at a time. The point where they meet is the duplicate number.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n), where n is the length of the arraySpace ComplexityO(1), since we only use two pointers

• The time complexity is O(n) because we traverse the array at most twice (once to find the cycle and once to find the duplicate).
• The space complexity is O(1) because we use only two pointers for detection.

🔍 Edge Cases

1. Small arrays: Arrays with only two elements (e.g., [1, 1]) where the duplicate is immediate.
2. Multiple duplicates: The problem guarantees there is only one duplicate; the algorithm will detect this one.
3. Large arrays: The algorithm is efficient with O(n) time and O(1) space, so it can handle large inputs within the constraints.

✅ Conclusion

LeetCode 287: Find the Duplicate Number is an excellent problem for practicing cycle detection and space optimization. Using Floyd's Tortoise and Hare algorithm, we can efficiently find the duplicate in a constant space and linear time.

This approach is useful for other problems involving cycles or linked list traversal, and can be extended to more general cycle detection in different contexts.