grid47 Exploring patterns and algorithms
Oct 9, 2024
5 min read
Solution to LeetCode 287: Find the Duplicate Number Problem
You are given an array nums of n + 1 integers where each integer is in the range [1, n]. The array contains exactly one duplicate number. Find and return this duplicate number without modifying the array and using constant extra space.
Problem
Approach
Steps
Complexity
Input: The input is an array `nums` containing `n + 1` integers. Each element is between 1 and `n` (inclusive).
Example: For example, `nums = [1, 2, 3, 4, 2]`.
Constraints:
• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All integers in `nums` appear only once except for one duplicate number.
Output: Return the duplicate number found in the array.
Example: For `nums = [1, 2, 3, 4, 2]`, the output should be `2`.
Constraints:
• The solution must be performed without modifying the array and using constant extra space.
Goal: Find the duplicate number in the array using the given constraints.
Steps:
• We will use a cycle detection approach (Floyd's Tortoise and Hare algorithm) to detect the duplicate number.
• Initialize two pointers `slow` and `fast`. The slow pointer moves one step at a time, while the fast pointer moves two steps.
• When both pointers meet, we reset one pointer to the start and move both pointers one step at a time until they meet again. The meeting point will be the duplicate number.
Goal: The solution should work within the time and space constraints.
Steps:
• The array should not be modified.
• Constant extra space should be used.
Assumptions:
• There is exactly one duplicate number in the array.
• The input array meets the constraints of having `n + 1` elements, with values between 1 and `n`.
• Input: For `nums = [1, 2, 3, 4, 2]`
• Explanation: The duplicate number in the array is `2`, as it appears twice.
• Input: For `nums = [5, 1, 3, 4, 5]`
• Explanation: The duplicate number in the array is `5`, as it appears twice.
• Input: For `nums = [6, 6, 6, 6, 6]`
• Explanation: All the numbers in the array are the same, and the duplicate number is `6`.
Approach: We can use Floyd's Tortoise and Hare algorithm (cycle detection) to detect the duplicate number in the array in linear time and constant space.
Observations:
• The problem can be reduced to finding a cycle in a linked list.
• Using two pointers at different speeds, we can detect a cycle and determine the duplicate number.
Steps:
• Start with two pointers: `slow` at the first element and `fast` at the second element (indexed by `nums[slow]`).
• Move the slow pointer by one step and the fast pointer by two steps until they meet. This detects the cycle.
• Once a cycle is detected, reset the fast pointer to the start of the array and move both pointers one step at a time until they meet. The meeting point is the duplicate number.
Empty Inputs:
• An empty array will not be provided based on the problem constraints.
Large Inputs:
• The solution should be able to handle large arrays with up to 100,000 elements.
Special Values:
• The array may contain all elements equal, in which case the duplicate will be the only number in the array.
Constraints:
• The solution must meet the constraints of constant extra space and linear runtime complexity.
intfindDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while(slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast =0;
while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return fast;
}
1 : Function Definition
intfindDuplicate(vector<int>& nums) {
Defines the function `findDuplicate`, which accepts a reference to a vector `nums` and finds the duplicate number using Floyd's Cycle-Finding Algorithm.
2 : Initialize Slow and Fast Pointers
int slow = nums[0], fast = nums[nums[0]];
Initializes two pointers: `slow` and `fast`. `slow` moves one step at a time, while `fast` moves two steps at a time.
3 : Cycle Detection Loop
while(slow != fast) {
Starts a loop to detect if there is a cycle. The loop continues until the slow and fast pointers meet.
4 : Move Slow Pointer
slow = nums[slow];
Moves the `slow` pointer one step ahead in the array.
5 : Move Fast Pointer
fast = nums[nums[fast]];
Moves the `fast` pointer two steps ahead by accessing the element at `nums[fast]` and then moving to `nums[nums[fast]]`.
6 : Reinitialize Fast Pointer
fast =0;
Reinitializes the `fast` pointer to the beginning of the array to find the entrance to the cycle.
7 : Start Second Loop
while(slow != fast) {
Starts a second loop to find the starting point of the cycle, which is where the duplicate number lies.
8 : Move Slow Pointer Again
slow = nums[slow];
Moves the `slow` pointer one step ahead.
9 : Move Fast Pointer Again
fast = nums[fast];
Moves the `fast` pointer one step ahead.
10 : Return Duplicate Number
return fast;
Returns the `fast` pointer, which now points to the duplicate number.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we iterate through the array a constant number of times.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we are only using two pointers, regardless of the array size.
