Find the Duplicate Number — Solution in Python, Java & C++
Find the Duplicate Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Duplicate Number is a medium coding problem on arrays, binary search and two pointers.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Two Pointers
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array nums of n + 1 integers where each integer is in [1, n], exactly one value is repeated (possibly more than twice). Return that repeated number without modifying the array and using only constant extra space.
Example 1
Input: nums = [1,3,4,2,2]
Output: 2
Example 2
Input: nums = [3,1,3,4,2]
Output: 3
Constraints
2 <= nums.length <= 311 <= nums[i] <= nums.length - 1Exactly one value repeats.
Hints for Find the Duplicate Number
Hint 1
Treat nums[i] as a pointer i → nums[i]; the repeat creates a cycle.
Hint 2
Floyd's tortoise-and-hare cycle detection finds the cycle entry — that's the duplicate.
How to solve Find the Duplicate Number
Read the array as a function: index i points to index nums[i]. Since there are n + 1 slots but values only in 1 .. n, two indices point to the same place — so following the pointers from index 0 must eventually enter a cycle, and the cycle's entrance is the duplicated value. Floyd's tortoise-and-hare finds it without touching the array or allocating anything.
Approach
- Move a slow pointer one step (
slow = nums[slow]) and a fast pointer two steps until they meet inside the cycle. - Reset the slow pointer to the start.
- Advance both one step at a time.
- Where they meet again is the cycle entrance, which is the duplicated value.
Why it works
The duplicate is the only value with two indices pointing at it, so it is exactly the node where two paths merge — the cycle's entrance. Floyd's second phase works because the distance from the start to the entrance equals the distance from the meeting point to the entrance, once you account for whole loops; walking both at the same speed therefore lands them together precisely there. This respects both constraints the problem imposes: the array is never modified and no extra space is used.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Both pointers must start from the same index, and the first phase must advance before comparing — otherwise they "meet" immediately at the start.
- Reset only the slow pointer for phase two; resetting both finds nothing.
- Sorting or marking the array is simpler but violates the no-modification rule.
- The value may repeat more than twice, which does not affect the argument — it still merges paths.
Reference solution
Python
from typing import List
def findDuplicate(nums: List[int]) -> int:
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowJava
public static int findDuplicate(int[] nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}C++
int findDuplicate(vector<int>& nums) {
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}JavaScript
var findDuplicate = function(nums) {
let slow = nums[0];
let fast = nums[nums[0]];
while (slow !== fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while (slow !== fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search