Find The Duplicate Number
To solve this coding challenge of finding the duplicate number in the given array
, 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
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
elements pointing to
possible index values.
Here's an extremely detailed explanation of how to solve the problem:
nums
n + 1
n + 1
n
# Explanation:
- Initialize Two Pointers:
-
Start with two pointers,
slow
fast
-
These pointers will help us to traverse the array in different paces; one moves one step at a time (
slow
fast
- Detect the Cycle:
-
Move
slow
slow
nums[slow]
-
Move
fast
fast
nums[nums[fast]]
-
Continue this process until
slow
fast
- Find the Entry Point of the Cycle:
-
After detecting the cycle, reset
fast
-
Move both
slow
fast
- They will meet at the entry point of the cycle, which corresponds to the duplicate number.
- Initialize Pointers:
- Cycle Detection:
- Reset Fast Pointer and Find Entry Point of the Cycle:
- Return the Duplicate Number:
Detailed Steps in Pseudocode:
# Initialize slow and fast pointers to the start of the array
slow = nums[0]
fast = nums[0]
# 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
# 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
# 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.