Find The Duplicate Number

To solve this coding challenge of finding the duplicate number in the given array
nums
, we can use a method that leverages the concept of Floyd's Tortoise and Hare (Cycle Detection). This method uses two pointers to detect cycles in the sequence of numbers, without modifying the array and using only constant extra space.
One primary idea behind this solution is that since numbers are in the range [1, n] and the array contains
n + 1
numbers, the sequence of numbers can be visualized as a linked list where each index points to another index in the array. A cycle is guaranteed to exist because there are
n + 1
elements pointing to
n
possible index values.
Here's an extremely detailed explanation of how to solve the problem:
# Explanation:
  1. Initialize Two Pointers:
    • Start with two pointers,
      slow
      and
      fast
      . Both pointers initially point to the first element of the array.
    • These pointers will help us to traverse the array in different paces; one moves one step at a time (
      slow
      ), while the other one moves two steps at a time (
      fast
      ).
  2. Detect the Cycle:
    • Move
      slow
      one step at a time, i.e.,
      slow
      moves to
      nums[slow]
      .
    • Move
      fast
      two steps at a time, i.e.,
      fast
      moves to
      nums[nums[fast]]
      .
    • Continue this process until
      slow
      and
      fast
      meet, indicating that a cycle is detected.
  3. Find the Entry Point of the Cycle:
    • After detecting the cycle, reset
      fast
      to the starting point of the array.
    • Move both
      slow
      and
      fast
      one step at a time from their current respective positions.
    • They will meet at the entry point of the cycle, which corresponds to the duplicate number.
    This method ensures that we only use constant extra space and never modify the array.
    Detailed Steps in Pseudocode:
  4. Initialize Pointers:
  5.                                             
    # Initialize slow and fast pointers to the start of the array
    slow = nums[0]
    fast = nums[0]
    
                                            
  6. Cycle Detection:
  7.                                             
    # Use a do-while loop to find the intersection point
    # Move slow pointer one step and fast pointer two steps
    do
    slow = nums[slow]          # Move slow one step
    fast = nums[nums[fast]]    # Move fast two steps
    while slow != fast             # Continue until they meet
    
                                            
  8. Reset Fast Pointer and Find Entry Point of the Cycle:
  9.                                             
    # Set fast pointer to the start of the array
    fast = nums[0]
    
    # Move both pointers one step at a time to find the entry point
    while slow != fast
    slow = nums[slow]          # Move slow one step
    fast = nums[fast]          # Move fast one step
    
                                            
  10. Return the Duplicate Number:
                                            
# The position where slow and fast meet is the duplicate number
return slow

                                        
Here is the complete pseudocode with all the comments and detailed explanation included within:
                                            
# Initialize the slow and fast pointers to the first element of the array
slow = nums[0]
fast = nums[0]

# Use a do-while loop to find the intersection point
# Move the slow pointer one step at a time,
# and the fast pointer two steps at a time until they meet
do
    slow = nums[slow]          # Slow pointer moves one step
    fast = nums[nums[fast]]    # Fast pointer moves two steps
while slow != fast             # Loop continues until slow meets fast

# Reset the fast pointer to the start of the array
fast = nums[0]

# Move both slow and fast pointers one step at a time
# until they meet at the entry point of the cycle
while slow != fast
    slow = nums[slow]          # Slow pointer moves one step
    fast = nums[fast]          # Fast pointer moves one step

# The meeting point is the entry to the cycle, hence the duplicate number
return slow

                                        
In this approach:
  • The time complexity is O(n), due to the two pointer traversals through the array.
  • The space complexity is O(1), as only two pointers are used.