Problem overview
The method findDuplicates(nums) receives an array of integers and returns a new array that holds each value that appears more than once. A value that shows up three times still appears only once in the result, and the result may be in any order.
For [2, 3, 1, 1, 4, 3, 2, 1], the values 1, 2 and 3 repeat (1 three times, 2 and 3 twice each) and 4 appears once. The answer is those three values in some order, for example [2, 1, 3] or [1, 3, 2]. The solution below returns [1, 3, 2], because it records a value at the moment its second copy is seen, and the second 1 comes first.
The lesson asks for O(n) time and O(n) extra space.
How to find duplicates in an array in JavaScript
There are three common ways to do it, and they differ in speed and in what they return.
- Nested loops. Compare every element with every later element. This takes
O(n²)time, so 100,000 numbers mean billions of comparisons. filterwithindexOf.nums.filter((v, i) => nums.indexOf(v) !== i)keeps every element whose first occurrence is earlier in the array. It reads well but hides the sameO(n²)cost, sinceindexOfscans the array on every call. It also returns a value once per extra copy: for the example it gives[1, 3, 2, 1], so it needs aSetaround it to remove repeats.- Counting in one pass. Remember how many times each value has been seen, and look the count up instead of rescanning. Each lookup in an object takes constant time on average, so the whole pass is
O(n). This is the lesson's approach.
Counting costs memory: the object can hold one entry per distinct value, which is where the O(n) extra space comes from. That is the trade: space for speed.
Step by step
- Create
result. An empty array declared withletcollects each duplicate as it is discovered. - Create
freq. An empty object maps each number to how many times it has appeared so far. Seeing a value a second time is how a duplicate is detected. - Loop over the values with
for (let value of nums).for...ofgives the values themselves, not the indices, which is all this problem needs. - Increase the count. Reading
freq[value]for a value that has not been seen givesundefined, andundefined + 1isNaN. Writing(freq[value] || 0)replaces the missing count with 0, so a first sighting becomes 1. - Check for exactly 2. The second sighting is the moment the value becomes a known duplicate.
- Push the value to
resultinside that check. - Return
result.
The test is for exactly 2, not "2 or more". With >= 2, a value that appears three times would be pushed on its second and its third sighting, and the result would hold it twice. Checking for 2 fires once per value, whatever the number of copies.
The solution in JavaScript
class Solution {
findDuplicates(nums) {
let result = [];
let freq = {};
for (let value of nums) {
freq[value] = (freq[value] || 0) + 1;
if (freq[value] == 2) {
result.push(value);
}
}
return result;
}
}
Tracing [2, 3, 1, 1, 4, 3, 2, 1]: the counts for 2, 3 and 1 reach 1 and nothing is pushed. The second 1 raises its count to 2, so 1 is pushed. The 4 is counted once. The second 3 pushes 3, the second 2 pushes 2, and the last 1 raises its count to 3, which is not 2, so nothing happens. The result is [1, 3, 2].
JavaScript details
- Object keys are strings.
freq[1]andfreq["1"]are the same entry. For an array of integers that is harmless, but an array holding both1and"1"would treat them as one value. AMapkeeps them apart, because it compares keys by value and type. - Plain objects inherit properties. Reading a key such as
"constructor"from{}finds a built-in function, notundefined, so the counting trick breaks on string keys like that. Integers are safe, which is why the lesson can use a plain object. For arbitrary data, use aMapor aSet. ==versus===. Herefreq[value] == 2compares two numbers, so either operator gives the same answer.===is the safer habit because it never converts types.letinfor...of. Each pass gets a freshvalue.constwould also work here, since the loop never reassigns it.
The same idea with a Set
If only the duplicates matter, and not the counts, two sets are enough: one for values seen once, one for duplicates.
function findDuplicates(nums) {
const seen = new Set();
const dups = new Set();
for (const v of nums) {
if (seen.has(v)) dups.add(v);
else seen.add(v);
}
return [...dups];
}
console.log(findDuplicates([2, 3, 1, 1, 4, 3, 2, 1]));
[ 1, 3, 2 ]
This version also works for strings and mixed data. To answer the yes/no question "does this array contain any duplicate?", one line is enough: new Set(nums).size !== nums.length.
Complexity
- Time:
O(n). The loop runs once per element, and each count update and lookup takes constant time on average. - Space:
O(n).freqholds up to n entries when all values are distinct, andresultholds at most n/2 values.
Edge cases and common mistakes
- Empty array or no repeats. The loop never pushes anything, so the method returns
[]. - All values equal.
[5, 5, 5, 5]returns[5], one entry, thanks to the exactly-2 test. - Negative numbers and zero. They work as keys:
[-1, -1, 0, 0]returns[-1, 0]. - Forgetting the
|| 0.freq[value] + 1on a new value givesNaN, andNaN == 2is never true, so nothing is ever found. - Using
>= 2. It adds a value again for each further copy. - Expecting a fixed order. The result lists values in the order their second copy appears. If a caller needs sorted output, sort the result afterwards with
result.sort((a, b) => a - b).
Testing
[2, 3, 1, 1, 4, 3, 2, 1]gives[1, 3, 2](same values as[2, 1, 3]).[1, 2, 3]gives[].[5, 5, 5, 5]gives[5].[1, 2, 2, 2, 1]gives[2, 1].
