Find the Duplicate Number medium

Problem Statement

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] (inclusive), prove that at least one duplicate number must exist. Find the duplicate number.

You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n^2).

Example 1:

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

Example 2:

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

Steps and Explanation

This problem can be efficiently solved using Floyd's Tortoise and Hare algorithm, also known as the cycle detection algorithm. The core idea is to treat the array as a linked list where each element nums[i] points to the element at index nums[i]. The presence of a duplicate number guarantees the existence of a cycle in this linked list.

1. Treat the array as a linked list: Imagine each number nums[i] as a pointer to the node at index nums[i].

2. Cycle Detection (Tortoise and Hare): The Tortoise and Hare algorithm is used to detect the presence of a cycle in a linked list.

   • A "tortoise" pointer moves one step at a time.
   • A "hare" pointer moves two steps at a time.
   • If a cycle exists, the tortoise and hare will eventually meet within the cycle.

3. Finding the Cycle Entry: Once the tortoise and hare meet, we reset the tortoise to the beginning of the array. We then move both the tortoise and hare one step at a time. The point where they meet again is the entry point of the cycle (the duplicate number).

Code

def findDuplicate(nums):
    """
    Finds the duplicate number in an array using Floyd's Tortoise and Hare algorithm.

    Args:
      nums: A list of integers.

    Returns:
      The duplicate number.
    """

    # Find the intersection point of the slow and fast pointers
    tortoise = nums[0]
    hare = nums[0]
    while True:
        tortoise = nums[tortoise]
        hare = nums[nums[hare]]
        if tortoise == hare:
            break

    # Find the entrance to the cycle
    tortoise = nums[0]
    while tortoise != hare:
        tortoise = nums[tortoise]
        hare = nums[hare]

    return tortoise

Complexity

• Time Complexity: O(n). The algorithm iterates through the array a constant number of times.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the tortoise and hare pointers.