Find All Duplicates in an Array — Problem & Solution
Find All Duplicates in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find All Duplicates in an Array is a medium coding problem on arrays and hash table, asked in Amazon, Google, Microsoft and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google, Microsoft, Flipkart
- 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 integer array nums of length n where every nums[i] is in the range [1, n] and each value appears once or twice, return all the values that appear twice, in increasing order.
Example 1
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
Example 2
Input: nums = [1,1,2]
Output: [1]
Example 3
Input: nums = [1]
Output: []
Constraints
1 <= nums.length <= 401 <= nums[i] <= nums.lengthEach element appears once or twice.
Follow-up: Can you do it in O(n) time using only the output array as extra space?
Hints for Find All Duplicates in an Array
Hint 1
The values are confined to
1..n, which means each one can index the array itself.Hint 2
Counting occurrences in an array of size n + 1 is the direct O(n) solution.
Hint 3
For O(1) extra space, negate
nums[abs(v) - 1]as a visited mark — meeting an already-negative slot means the second sighting.
How to solve Find All Duplicates in an Array
Values are confined to 1..n, so a counting array of size n + 1 records each value's frequency; report those counted twice.
Approach
- Allocate
countof sizen + 1. - Increment
count[x]for each element. - Collect every
vin1..nwithcount[v] == 2, in increasing order.
Why it works
Iterating v from 1 to n visits values in sorted order, so the output is sorted without an explicit sort.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- For O(1) extra space, negate
nums[|v| - 1]as a visited mark and report|v|when the slot is already negative — then sort the result. - A hash set works but the bounded range makes the array strictly better.
Reference solution
Python
def findDuplicates(nums):
count = [0] * (len(nums) + 1)
for x in nums:
count[x] += 1
return [v for v in range(1, len(nums) + 1) if count[v] == 2]Java
public static int[] findDuplicates(int[] nums) {
int[] count = new int[nums.length + 1];
for (int x : nums) count[x]++;
List<Integer> out = new ArrayList<>();
for (int v = 1; v <= nums.length; v++) {
if (count[v] == 2) out.add(v);
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> findDuplicates(vector<int>& nums) {
vector<int> count(nums.size() + 1, 0);
for (int x : nums) count[x]++;
vector<int> out;
for (int v = 1; v <= (int) nums.size(); v++) {
if (count[v] == 2) out.push_back(v);
}
return out;
}JavaScript
var findDuplicates = function(nums) {
const count = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) count[nums[i]]++;
const out = [];
for (let v = 1; v <= nums.length; v++) {
if (count[v] === 2) out.push(v);
}
return out;
};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 · Hashing: Hash Maps and Hash Sets