Find the Duplicate Number solution and explanation
Google
TCS
Cisco
9 more videos on this problem
Find the Duplicate Number - Floyd's Cycle Detection - Leetcode 287 - PythonNeetCode · 17:34 · 464K views
Find the duplicate number (LeetCode 287) | Full solution with different methods | Study AlgorithmsNikhil Lohia · 18:14 · 80K views
Duplicate number in an immutable array | Floyd cycle detection algo | Leetcode #287Techdose · 19:18 · 48K views
Find the Duplicate Number | With Proof | Follow Up Qns | Hare And Tortoise | Leetcode - 287codestorywithMIK · 26:47 · 28K views
Find the Duplicate Number | LeetCode 287 | C++, Java, PythonKnowledge Center · 13:56 · 15K views
Floyd’s Algorithm for Cycle Detection | LeetCode 287. Find the Duplicate Number | Part 2Shiran Afergan · 9:17 · 7K views
Full Thought Process | LeetCode 287. Find the Duplicate Number | Part 1Shiran Afergan · 11:06 · 4K views
Leetcode 287. Find the Duplicate Number - Microsoft Interview QuestionCode with Carter · 8:17 · 4K views
Find the Duplicate Number - Leetcode 287 - PythonTechError · 6:12 · 3K views
Leetcode | 287. Find the Duplicate Number | Medium | Java SolutionDeveloper Docs · 5:22 · 2K views
The problem
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: 2
Example 2:
Input: nums = [3,1,3,4,2] Output: 3
Example 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?
Approach overview
Problem Overview: You receive an array of n + 1 integers where each value is in the range [1, n]. Since there are more numbers than the range allows, at least one value must appear more than once. The task is to return the duplicate number without modifying the array and while using minimal extra space.
Approach 1: Floyd's Tortoise and Hare (Cycle Detection) (O(n) time, O(1) space)
This approach treats the array like a linked list. Each index points to the next index using the value stored at that position. Because values are restricted to 1..n, following these "next" pointers must eventually form a cycle. The duplicate number is exactly the entry point of that cycle. Use two pointers: a slow pointer moving one step at a time and a fast pointer moving two steps. When they meet, a cycle exists. Reset one pointer to the start and move both one step at a time until they meet again; that position corresponds to the duplicate value. This technique uses the classic two pointers pattern and works without modifying the array. Time complexity is O(n) because each pointer traverses the structure at most a few passes. Space complexity is O(1) since only a couple of variables are used.
Approach 2: Binary Search on Result (O(n log n) time, O(1) space)
This method applies binary search on the value range instead of array indices. The key insight comes from the pigeonhole principle. For any midpoint mid, count how many numbers in the array are less than or equal to mid. If the count exceeds mid, the duplicate must lie in the range [1, mid]. Otherwise, it lies in [mid + 1, n]. Repeatedly narrow the search range until a single value remains. Each step scans the array once to compute the count, giving O(n) work per iteration and O(log n) iterations overall. The algorithm uses constant extra memory and does not modify the input.
Recommended for interviews: Floyd's cycle detection is the solution most interviewers expect. It demonstrates deeper algorithmic thinking because you reinterpret the array as a linked structure and apply cycle detection to locate the repeated value. The binary search approach is also valid and easier to reason about, but it is slower at O(n log n). Showing the binary search idea first and then optimizing to Floyd's algorithm signals strong problem-solving skills.
Approach 1: Approach 1: Floyd's Tortoise and Hare (Cycle Detection)
This approach uses cycle detection to find the duplicate number using two pointers. Imagine the numbers in the array form a linked list, where the value at each index points to the next index. When there is a duplicate, a cycle will be formed. The first step is to find the intersection point of the cycle using a slow and fast pointer. Once they meet, use two pointers to find the entrance of the cycle, which will be the duplicate number. This method doesn't modify the array and uses O(1) space.
def findDuplicate(nums):
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
public class Solution {
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;
}
}
class Solution {
public:
int findDuplicate(vector<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;
}
};
var findDuplicate = function(nums) {
let slow = nums[0];
let 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;
};
int findDuplicate(int* nums, int numsSize) {
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;
}
public class Solution {
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;
}
}This Python implementation uses a Floyd's cycle-finding algorithm to locate the duplicate number without modifying the input array and using constant extra space.
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Approach 2: Binary Search on Result
This approach leverages a binary search technique on the range of possible values of the duplicate number. For each midpoint in this range, count how many numbers are less than or equal to it. If the count is greater than the midpoint, the duplicate must be in the lower range; otherwise, it is in the upper range. Binary search is applied until the duplicate is found. This doesn't require additional space and doesn't alter the input array.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
count = sum(num <= mid for num in nums)
if count > mid:
high = mid
else:
low = mid + 1
return low
public class Solution {
public int findDuplicate(int[] nums) {
int low = 1, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0;
for (int num : nums) {
if (num <= mid) count++;
}
if (count > mid) high = mid;
else low = mid + 1;
}
return low;
}
}
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int low = 1, high = nums.size() - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0;
for (int num : nums) {
if (num <= mid) count++;
}
if (count > mid) high = mid;
else low = mid + 1;
}
return low;
}
};
var findDuplicate = function(nums) {
let low = 1, high = nums.length - 1;
while (low < high) {
let mid = Math.floor((low + high) / 2);
let count = 0;
for (let num of nums) {
if (num <= mid) count++;
}
if (count > mid) high = mid;
else low = mid + 1;
}
return low;
};
int findDuplicate(int* nums, int numsSize) {
int low = 1, high = numsSize - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= mid) count++;
}
if (count > mid) high = mid;
else low = mid + 1;
}
return low;
}
public class Solution {
public int FindDuplicate(int[] nums) {
int low = 1, high = nums.Length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
int count = 0;
foreach (int num in nums) {
if (num <= mid) count++;
}
if (count > mid) high = mid;
else low = mid + 1;
}
return low;
}
}This Python implementation applies a binary search to estimate the duplicate number, counting the occurrences of numbers less than or equal to the mid, then adjusting the search range.
Time Complexity: O(n log n). Space Complexity: O(1).
Approach 3: Binary Search
We can observe that if the number of elements in [1,..x] is greater than x, then the duplicate number must be in [1,..x], otherwise the duplicate number must be in [x+1,..n].
Therefore, we can use binary search to find x, and check whether the number of elements in [1,..x] is greater than x at each iteration. This way, we can determine which interval the duplicate number is in, and narrow down the search range until we find the duplicate number.
The time complexity is O(n times log n), where n is the length of the array nums. The space complexity is O(1).
function findDuplicate(nums: number[]): number {
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;
}func findDuplicate(nums []int) int {
return sort.Search(len(nums), func(x int) bool {
cnt := 0
for _, v := range nums {
if v <= x {
cnt++
}
}
return cnt > x
})
}impl Solution {
#[allow(dead_code)]
pub fn find_duplicate(nums: Vec<i32>) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = (left + right) >> 1;
let cnt = nums.iter().filter(|x| **x <= (mid as i32)).count();
if cnt > mid {
right = mid;
} else {
left = mid + 1;
}
}
left as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Floyd's Tortoise and Hare (Cycle Detection) | Time Complexity: O(n). Space Complexity: O(1). |
| Approach 2: Binary Search on Result | Time Complexity: O(n log n). Space Complexity: O(1). |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd's Tortoise and Hare (Cycle Detection) | O(n) | O(1) | Optimal interview solution when array cannot be modified and constant space is required |
| Binary Search on Value Range | O(n log n) | O(1) | Useful when you recognize the pigeonhole principle and want a simpler reasoning approach |
Frequently asked questions
Is Find the Duplicate Number easy or hard?
Find the Duplicate Number is rated Medium difficulty. The brute reasoning is straightforward, but recognizing that the array forms a cycle and applying Floyd's algorithm requires deeper algorithmic insight.
Find the Duplicate Number Python/Java solution
Python and Java implementations usually follow Floyd's cycle detection pattern: run a slow and fast pointer until they meet, then reset one pointer to the start and move both step by step to locate the duplicate. The algorithm uses constant space and runs in linear time.
How to solve Find the Duplicate Number in O(n)?
Use Floyd's Tortoise and Hare algorithm. Move a slow pointer by one step and a fast pointer by two steps through indices defined by array values until they meet. Reset one pointer to the start and move both one step at a time; the meeting point identifies the duplicate number.
What is the best approach for Find the Duplicate Number?
Floyd's Tortoise and Hare cycle detection algorithm is the optimal approach. It runs in O(n) time and O(1) space while keeping the array unchanged. The trick is modeling the array as a linked list where each value points to the next index, which naturally forms a cycle at the duplicate.
Is Find the Duplicate Number asked at Google/Amazon/Meta?
Find the Duplicate Number frequently appears in interviews at companies like Google, Amazon, and Meta. It tests understanding of cycle detection, pointer techniques, and reasoning about constraints such as not modifying the input array and using constant extra space.
What data structure is used in Find the Duplicate Number?
The problem uses an array as the input structure, but the optimal solution conceptually treats it like a linked list. Each index points to another index based on its value, allowing cycle detection techniques with two pointers to identify the duplicate.
What is the time complexity of Find the Duplicate Number?
The optimal solution using Floyd's cycle detection runs in O(n) time with O(1) extra space. Another common method uses binary search on the value range, which takes O(n log n) time because each binary search step requires scanning the entire array.