Find the Duplicate Number
MedPrompt
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and using only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2Example 2:
Input: nums = [3,1,3,4,2]
Output: 3Example 3:
Input: nums = [3,3,3,3,3]
Output: 3
Constraints:
1 <= n <= 105nums.length == n + 11 <= nums[i] <= n- All the integers in
numsappear only once except for precisely one integer which appears two or more times.
Follow up:
- How can we prove that at least one duplicate number must exist in
nums? - Can you solve the problem in linear runtime complexity?
Approaches
3 approaches with complexity analysis and trade-offs.
Treat array elements as pointers to indices and use Floyd's cycle detection algorithm to find the duplicate.
Algorithm
- Initialize two pointers (tortoise and hare) at the start
- Move tortoise one step and hare two steps until they meet
- Reset tortoise to start
- Move both pointers one step until they meet again
- Return the meeting point as the duplicate
Walkthrough
This approach uses Floyd's Cycle Detection algorithm. Since the numbers are in range [1,n] and there's a duplicate, we can treat array values as pointers forming a linked list, which will have a cycle. The duplicate number is the entry point of the cycle.
public int findDuplicate(int[] nums) { // Find the intersection point of the two pointers int tortoise = nums[0]; int hare = nums[0]; do { tortoise = nums[tortoise]; hare = nums[nums[hare]]; } while (tortoise != hare); // Find the entrance to the cycle tortoise = nums[0]; while (tortoise != hare) { tortoise = nums[tortoise]; hare = nums[hare]; } return hare;}Complexity
Time
O(n) - where n is the length of the array
Space
O(1) - only using two pointers
Trade-offs
Pros
Optimal time complexity
Constant space complexity
No modification to original array
Meets all problem constraints
Cons
More complex to understand
Requires understanding of cycle detection concept
Solutions
Solution
class Solution {public int findDuplicate(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { int mid = (l + r) >> 1; int cnt = 0; for (int v : nums) { if (v <= mid) { ++cnt; } } if (cnt > mid) { r = mid; } else { l = mid + 1; } } return l; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.