Find the Duplicate Number
Find the Duplicate Number is a medium linked list problem solved with the slow fast pointers pattern.
The best approach, optimal (floyd's cycle detection), runs in O(n) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair) up.
Problem
You get an array nums with n + 1 integers, and every integer lies between 1 and n inclusive. By the pigeonhole principle at least one value must repeat; here exactly one value is repeated, though it may occur more than twice.
Return that repeated value. Solve it without changing nums and with only constant extra memory.
Examples
Example 1
- Input
nums = [3,1,4,2,4]- Output
4- Why
- Values run from 1 to 4 across five slots; 4 is the one that appears twice.
Example 2
- Input
nums = [2,5,2,1,2,3]- Output
2- Why
- The repeated value may show up more than twice: here 2 appears three times.
Example 3
- Input
nums = [1,1]- Output
1- Why
- The smallest case: n = 1, so both slots hold 1.
Constraints
1 <= n <= 10^5nums.length == n + 11 <= nums[i] <= n- Exactly one value appears two or more times; every other value appears at most once.
- Do not modify
nums, and use only O(1) extra space in the final solution.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare every pair) | O(n²) | O(1) |
| Binary search on the value range | O(n log n) | O(1) |
| Optimal (Floyd's cycle detection) | O(n) | O(1) |
1Brute force (compare every pair)
O(n²)About n² / 2 pairs in the worst case.O(1)Only loop indices.Check every pair of indices i < j. The first pair holding equal values reveals the duplicate.
- For i from 0 to n: for j from i + 1 to n: if nums[i] == nums[j], return nums[i].
class Solution {
public int findDuplicate(int[] nums) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] == nums[j]) return nums[i];
return -1;
}
}class Solution:
def findDuplicate(self, nums: List[int]) -> int:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return nums[i]
return -1class Solution {
public:
int findDuplicate(vector<int>& nums) {
for (int i = 0; i < (int)nums.size(); i++)
for (int j = i + 1; j < (int)nums.size(); j++)
if (nums[i] == nums[j]) return nums[i];
return -1;
}
};function findDuplicate(nums) {
for (let i = 0; i < nums.length; i++)
for (let j = i + 1; j < nums.length; j++)
if (nums[i] === nums[j]) return nums[i];
return -1;
}2Binary search on the value range
O(n log n)log n rounds, each counting over the whole array.O(1)A few integer variables; the array is only read.For a candidate value mid, count the elements <= mid. Without a duplicate at or below mid, that count is at most mid. If it is larger, the duplicate is in [1, mid]; otherwise it is in [mid + 1, n]. Shrink the range until one value is left.
- lo = 1, hi = n.
- While lo < hi: mid = (lo + hi) / 2; cnt = number of x in nums with x <= mid.
- If cnt > mid: hi = mid; else lo = mid + 1.
- Return lo.
class Solution {
public int findDuplicate(int[] nums) {
int lo = 1, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int x : nums) if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}
}class Solution:
def findDuplicate(self, nums: List[int]) -> int:
lo, hi = 1, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
cnt = sum(1 for x in nums if x <= mid)
if cnt > mid:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public:
int findDuplicate(vector<int>& nums) {
int lo = 1, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int cnt = 0;
for (int x : nums) if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}
};function findDuplicate(nums) {
let lo = 1, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
let cnt = 0;
for (const x of nums) if (x <= mid) cnt++;
if (cnt > mid) hi = mid;
else lo = mid + 1;
}
return lo;
}3Optimal (Floyd's cycle detection)
O(n)Both phases take at most a constant number of laps over the path of length n + 1.O(1)Two pointers; the array is never written.Treat each index as a node with one outgoing edge to nums[i]. Index 0 has no incoming edge from a value (values are at least 1), and because two indices point to the same value, the path from 0 runs into a cycle whose entry node is the duplicate. Run the tortoise (one step) and hare (two steps) until they meet inside the cycle, then restart one pointer at 0 and move both one step at a time; they meet at the entrance.
- 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.
class Solution {
public 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;
}
}class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = nums[0], 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 slowclass Solution {
public:
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;
}
};function findDuplicate(nums) {
let 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;
}Edge cases to test
- The smallest input
[1, 1] - The duplicate fills almost every slot, e.g.
[3, 3, 3, 3] - The duplicate is 1 or n (the edges of the value range)
- Some values in 1..n are missing because the duplicate took their place
- The repeated copies sit at the very first and very last index
Hints
Hint 1
There are n + 1 slots but only n possible values, so some value must repeat. Comparing every pair finds it, but slowly.
Hint 2
Count how many elements are <= mid. If that count is greater than mid, the duplicate lies in [1, mid]. That gives a binary search over values.
Hint 3
Read the array as a function i -> nums[i]. Starting from index 0 and following it forms a path that ends in a cycle, and the cycle's entrance is the duplicate. Floyd's tortoise and hare finds it in O(1) space.
FAQ
What is the best time complexity for Find the Duplicate Number?
Optimal (Floyd's cycle detection) runs in O(n) time and O(1) extra space. Both phases take at most a constant number of laps over the path of length n + 1.
Which pattern does Find the Duplicate Number use?
It is a linked list problem that uses the slow fast pointers pattern. Other problems with the same pattern: Middle of the Linked List, Linked List Cycle, Linked List Cycle II.
Is there a brute force solution for Find the Duplicate Number?
Yes. Brute force (compare every pair) takes O(n²) time and O(1) space. Check every pair of indices i < j.
Which edge cases should I test for Find the Duplicate Number?
The smallest input [1, 1]; The duplicate fills almost every slot, e.g. [3, 3, 3, 3]; The duplicate is 1 or n (the edges of the value range); Some values in 1..n are missing because the duplicate took their place; The repeated copies sit at the very first and very last index.