Problem overview
The method removeDuplicates receives an array of integers, nums, and returns a new array that holds each value once. The order of the result does not matter.
For [2, 3, 1, 1, 4, 3, -2, 1] the answer is the five distinct values 2, 3, 1, 4, -2, in any order.
Approach: let a set do the work
The statement asks for O(n) time and O(n) extra space. Checking for each element whether it already appeared in the output by scanning the output would cost O(n²). Sorting first and dropping neighbours that match costs O(n log n).
A Set removes duplicates by design: it stores each value once, and adding a value costs O(1) on average. So the whole job is two conversions. Array to set drops the repeats. Set to array gives the result back in the type the method must return.
Step by step
- Build the set.
const uniqueValues = new Set(nums). The constructor accepts any iterable, and an array is one. The compiler infersSet<number>fromnums, so no type argument is needed. - Convert back with spread.
[...uniqueValues]expands the set into the elements of a new array, which the method returns.
The solution in TypeScript
class Solution {
removeDuplicates(nums: number[]): number[] {
const uniqueValues = new Set(nums);
return [...uniqueValues];
}
}- The result is a new array.
numsis not changed. - The order is the first-seen order. A
Setremembers insertion order, so the example returns[2, 3, 1, 4, -2]. The lesson accepts any order, but this one comes for free. - Return type. Returning
uniqueValuesitself would be a compiler error, because aSet<number>is not anumber[].Array.from(uniqueValues)does the same job as the spread. - Spreading needs an iterable. The lessons compile for ES2022, where spreading a set works directly.
Other ways, and why they fall short
The same result can be written with the array's own methods:
function viaFilter(nums: number[]): number[] {
return nums.filter((v, i) => nums.indexOf(v) === i);
}This keeps an element only if its first occurrence is at its own position, and it returns [2, 3, 1, 4, -2] on the example. But indexOf scans from the start every time, so the whole thing is O(n²).
Written as an explicit loop, the set-based version looks like this:
function viaLoop(nums: number[]): number[] {
const seen = new Set<number>();
const out: number[] = [];
for (const v of nums) {
if (!seen.has(v)) {
seen.add(v);
out.push(v);
}
}
return out;
}It does the work the constructor already does, with the same O(n) cost. The two-line solution is the better one to write, and it is also the clearest to read.
A plain object used as a set has a trap of its own: object keys are always strings, so after obj[v] = true for the values 1, 2 and 1, Object.keys(obj) is ['1', '2'], strings and not numbers. A Set keeps the numbers as numbers.
Complexity
Time: O(n). Building the set visits each element once, and copying it into an array visits each distinct value once.
Space: O(n). The set and the result array each hold up to n values.
Edge cases and common mistakes
- Negative numbers.
-2is an ordinary value to a set, so it appears once like any other. - Empty input.
[]gives[]. - Everything equal.
[5, 5, 5]gives[5]. - Mixed zero signs.
0and-0are one value for a set, so[0, -0]gives[0]. - Using the set as the result. It is not an array: it has no
length, no indexing and nomap. - Relying on types at run time. If the array secretly contained the string
"1"as well as the number1, the set would keep both, since annotations are erased when compiling.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives[2, 3, 1, 4, -2].[]gives[].[7, 7]gives[7].