Find All Duplicates in an Array
Find All Duplicates in an Array is a medium arrays & hashing problem solved with the in-place transformations pattern.
The best approach, optimal (index marking with signs), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (hash set) up.
Problem
You get an array of n integers where every value is in [1, n] and appears once or twice. Return all values that appear twice.
Solve it in O(n) time using only constant extra space.
Examples
Example 1
- Input
nums = [3, 1, 3, 4, 2, 4]- Output
[3, 4]
Example 2
- Input
nums = [1, 2]- Output
[]
Constraints
1 <= n <= 10^51 <= nums[i] <= n, each value appears once or twice.- O(n) time and constant extra space.
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 (2 examples, or your own). Submit also runs 10 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.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
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 (hash set) | O(n) | O(n) |
| Optimal (index marking with signs) | O(n) | O(1) |
1Brute force (hash set)
O(n)O(n)Add values to a set; a value already in the set is a duplicate.
- For each x: if the set contains x, record it; else add it.
class Solution {
public List<Integer> findDuplicates(int[] nums) {
Set<Integer> seen = new HashSet<>();
List<Integer> out = new ArrayList<>();
for (int x : nums) if (!seen.add(x)) out.add(x);
return out;
}
}class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
seen = set()
out = []
for x in nums:
if x in seen:
out.append(x)
else:
seen.add(x)
return outclass Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
unordered_set<int> seen;
vector<int> out;
for (int x : nums) if (!seen.insert(x).second) out.push_back(x);
return out;
}
};function findDuplicates(nums) {
const seen = new Set();
const out = [];
for (const x of nums) {
if (seen.has(x)) out.push(x);
else seen.add(x);
}
return out;
}2Optimal (index marking with signs)
O(n)O(1)The input array stores the markers; only the output is extra.For value v, flip nums[v - 1] to negative to mark v as seen. If it is already negative when you arrive, v is a duplicate. Use Math.abs when reading, since earlier steps may have flipped the current cell.
- For each i: v = |nums[i]|.
- If nums[v - 1] < 0, add v to the answer.
- Else set nums[v - 1] = -nums[v - 1].
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> out = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int v = Math.abs(nums[i]);
if (nums[v - 1] < 0) out.add(v);
else nums[v - 1] = -nums[v - 1];
}
return out;
}
}class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
out = []
for i in range(len(nums)):
v = abs(nums[i])
if nums[v - 1] < 0:
out.append(v)
else:
nums[v - 1] = -nums[v - 1]
return outclass Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> out;
for (int i = 0; i < (int) nums.size(); i++) {
int v = abs(nums[i]);
if (nums[v - 1] < 0) out.push_back(v);
else nums[v - 1] = -nums[v - 1];
}
return out;
}
};function findDuplicates(nums) {
const out = [];
for (let i = 0; i < nums.length; i++) {
const v = Math.abs(nums[i]);
if (nums[v - 1] < 0) out.push(v);
else nums[v - 1] = -nums[v - 1];
}
return out;
}Edge cases to test
- No duplicates
- Every value duplicated
Hints
Hint 1
Values are 1..n, so every value maps to an index. Can the sign of nums[v - 1] remember that v was seen?
FAQ
What is the best time complexity for Find All Duplicates in an Array?
Optimal (index marking with signs) runs in O(n) time and O(1) extra space.
Which pattern does Find All Duplicates in an Array use?
It is a arrays & hashing problem that uses the in-place transformations pattern. Other problems with the same pattern: Set Matrix Zeroes, First Missing Positive, Rotate Image.
Is there a brute force solution for Find All Duplicates in an Array?
Yes. Brute force (hash set) takes O(n) time and O(n) space. Add values to a set; a value already in the set is a duplicate.
Which edge cases should I test for Find All Duplicates in an Array?
No duplicates; Every value duplicated.