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
Compare each element with every other element in the array to find the duplicate number.
Algorithm
- Iterate through the array with index i from 0 to n-1
- For each i, iterate through the array with index j from i+1 to n-1
- If nums[i] equals nums[j], return nums[i]
- If no duplicate is found, return -1
Walkthrough
This approach involves using two nested loops to compare each element with every other element in the array. When we find two elements that are equal, we return that number as the duplicate.
public int findDuplicate(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[i] == nums[j]) { return nums[i]; } } } return -1;}Complexity
Time
O(n²) - where n is the length of the array as we use two nested loops
Space
O(1) - only using constant extra space
Trade-offs
Pros
Simple to understand and implement
No extra space required
No modification to original array
Cons
Very inefficient for large arrays
Time complexity is quadratic
Sort the array first and then check adjacent elements for duplicates.
Algorithm
- Create a copy of the input array
- Sort the copied array
- Iterate through the sorted array
- Check if current element equals previous element
- If equal, return the element
Walkthrough
This approach first sorts the array (creating a copy to not modify the original) and then checks adjacent elements to find the duplicate. When two adjacent elements are equal, we've found our duplicate.
public int findDuplicate(int[] nums) { int[] sorted = nums.clone(); Arrays.sort(sorted); for (int i = 1; i < sorted.length; i++) { if (sorted[i] == sorted[i-1]) { return sorted[i]; } } return -1;}Complexity
Time
O(n log n) - due to the sorting operation
Space
O(n) - need extra space for the sorted copy of the array
Trade-offs
Pros
Relatively simple to implement
No modification to original array
Cons
Not optimal time complexity
Requires extra space
Doesn't meet the constant space requirement
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; }}/** * @param {number[]} nums * @return {number} */ var findDuplicate = function (nums) { let l = 0; let r = nums.length - 1; while (l < r) { const mid = (l + r) >> 1; let cnt = 0; for (const v of nums) { if (v <= mid) { ++cnt; } } if (cnt > mid) { r = mid; } else { l = mid + 1; } } return l; };class Solution {public: int findDuplicate(vector<int> &nums) { int l = 0, r = nums.size() - 1; while (l < r) { int mid = (l + r) >> 1; int cnt = 0; for (int &v : nums) { cnt += v <= mid; } if (cnt > mid) { r = mid; } else { l = mid + 1; } } return l; }};class Solution: def findDuplicate(self, nums: List[int]) -> int: def f(x: int) -> bool: return sum(v <= x for v in nums) > x return bisect_left(range(len(nums)), True, key=f)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.