LeetCode 287: Find the Duplicate Number Solution
Master LeetCode problem 287 (Find the Duplicate Number), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
287. Find the Duplicate Number
Problem Explanation
Explanation
To solve this problem without modifying the array and using only constant extra space, we can use the Floyd's Tortoise and Hare algorithm. This algorithm is commonly used to detect cycles in a linked list but can also be applied to this problem as the array can be visualized as a linked list where the value at each index points to the next index.
- Initialize two pointers, slow and fast, both starting at the first index.
- Move the slow pointer one step and the fast pointer two steps at a time until they meet at some index.
- Once they meet, reset the slow pointer to the first index and move both slow and fast pointers one step at a time until they meet again. The index at which they meet is the duplicate number.
This algorithm guarantees finding a duplicate number because there must be a cycle in the array due to the constraint that one number appears two or more times.
- Time complexity: O(n)
- Space complexity: O(1)
Solution Code
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 287 (Find the Duplicate Number)?
This page provides optimized solutions for LeetCode problem 287 (Find the Duplicate Number) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 287 (Find the Duplicate Number)?
The time complexity for LeetCode 287 (Find the Duplicate Number) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 287 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 287 in Java, C++, or Python.