Problem overview
The method findDuplicates receives an array of integers, nums, and returns a new array with the values that appear more than once. Each duplicated value is listed once, however many copies there are, and the order of the result does not matter.
For [2, 3, 1, 1, 4, 3, 2, 1], the values 1, 2 and 3 repeat, and 4 appears once. The answer holds exactly those three values. The solution below returns them as [1, 3, 2], which is an acceptable order.
Approach: count as you go
The statement asks for O(n) time and O(n) extra space. Comparing every pair of elements would take O(n²). Instead, keep a frequency table that maps each value to the number of times it has appeared so far, and update it in a single pass.
The key observation is when to report a value. A value is a duplicate the moment its count reaches exactly 2. Counts of 3, 4 and beyond are the same value appearing again, so they must not be reported again. Testing for == 2, not >= 2, is what gives each duplicate exactly one entry in the result.
On the example, the running counts show which element triggers each report: the second 1 (index 3), the second 3 (index 5) and the second 2 (index 6). The third 1 at the end brings that count to 3, which is not 2, so it is ignored.
Step by step
- Create the result.
resultis an emptynumber[]that collects duplicates as they are discovered. - Create the frequency table.
freqis an object typed{ [key: number]: number }, an index signature saying "numeric keys, numeric values". - Loop over the values. A
for...ofloop gives each number asvalue. - Increase the count. Reading a key that was never set gives
undefined, andundefined + 1isNaN. The|| 0turns that missing count into0first. - Test for exactly 2. That is the moment the second copy shows up.
- Record the duplicate. Push
valueontoresult, once per duplicated value. - Return
result.
The solution in TypeScript
class Solution {
findDuplicates(nums: number[]): number[] {
let result: number[] = [];
let freq: { [key: number]: number } = {};
for (const value of nums) {
freq[value] = (freq[value] || 0) + 1;
if (freq[value] == 2) {
result.push(value);
}
}
return result;
}
}The TypeScript details to know:
- Object keys are strings. Even with the number-keyed type,
freq[3]andfreq["3"]are the same property at run time. Negative numbers work too:-2becomes the key"-2". - The index signature is a promise, not a check. The type says
freq[value]is anumber, but for a missing key the value isundefined. The compiler does not warn about it, which is why the|| 0fallback is necessary. ||versus??. A count is never0once stored, so||is safe here.??would also work and says more precisely "only when missing".==versus===. Both are fine for comparing two numbers.===is the usual habit, since it never converts types.- A
Mapis the other option.Map<number, number>keeps keys as numbers and hasgetwith a default via?? 0. For this lesson an object is enough.
An alternative with two sets
If you only need to know whether a value repeated, and not how many times, two sets do the same job:
function withSets(nums: number[]): number[] {
const seen = new Set<number>();
const duplicates = new Set<number>();
for (const value of nums) {
if (seen.has(value)) {
duplicates.add(value);
} else {
seen.add(value);
}
}
return [...duplicates];
}It also returns [1, 3, 2] on the example. Here the second set removes the need for the "exactly 2" trick: adding a value to a set twice is harmless. The lesson's version needs only one structure, and a counting table is the better tool when a later problem asks how often a value occurs.
Why not the brute force
The obvious first attempt compares each element with every later one, and records a value when a match is found. That needs extra care to avoid listing a value twice, for example by checking the result with includes, and its running time grows with the square of the array length. The frequency table replaces all of that comparing with one lookup per element.
Complexity
Time: O(n). One pass, and each iteration does a constant number of property reads and writes, which take O(1) time on average.
Space: O(n). freq holds one entry per distinct value, and result holds at most n / 2 values.
Edge cases and common mistakes
- Empty array. The loop never runs and the result is
[]. - No duplicates.
[1, 2, 3]gives[]. - A value repeated many times.
[5, 5, 5, 5]gives[5], not four copies. The test== 2fires only once. - Testing
>= 2. The third and fourth copies would push the value again, so[5, 5, 5, 5]would give[5, 5, 5]. - Forgetting the fallback. Without
|| 0, the first sighting storesNaN. The count never equals 2, and no duplicates are found. - Zero and negatives.
[-1, -1, 0, 0]gives[-1, 0]. Keys like"-1"and"0"are ordinary property names. - Checking the count too early. The test must come after the increment. Testing before it would look for a count of
2one element too late.
Testing
[2, 3, 1, 1, 4, 3, 2, 1]gives[1, 3, 2], the same values as the statement's example in a different order.[]gives[].[5, 5, 5, 5]gives[5].[-1, -1, 0, 0]gives[-1, 0].