LESSON 196 OF 348 · NESTED LOOPS & BRUTE FORCE

Remove Duplicates From Array in TypeScript: O(n^2) with includes

Practice O(n²) Read the full explanation

Given an array of integers, return a new array containing only the unique values.

The resulting array can be in any order.

Example:

Input: [2, 3, 1, 1, 4, 3, -2, 1]
Output: [2, 3, 1, 4, -2]

Note:

For this lesson, your algorithm should run in O(n^2) time and use O(n) extra space.
(There are faster solutions which we will discuss in future lessons)

Hints:

Let's use an extra array uniqueVals and push the unique values from nums there. We can traverse the array nums from left to right using an index i. We should push nums[i] into uniqueVals only if that value has not been seen before. How can we check this?

nums[i] has never been seen before if it doesn't occur in uniqueVals.

STEP 1 OF 4

Guided

Ctrl + Enter to check

TYPESCRIPT · NESTED LOOPS & BRUTE FORCE

Remove Duplicates From Array in TypeScript, explained

Problem overview

The method removeDuplicates receives an array of numbers, nums, and returns a new array that contains each distinct value once. The order of the result may be anything. The input [2, 3, 1, 1, 4, 3, -2, 1] gives [2, 3, 1, 4, -2], because the values 1 and 3 appear several times in the input but only once in the output.

The statement sets a budget of O(n^2) time and O(n) extra space: the answer is built in a second array, and finding out whether a value is already in it is allowed to be slow.

Approach: keep a list of what you have seen

Go through nums from left to right and keep a second array, uniqueValues. For each value, ask one question: is it already in uniqueValues? If not, this is its first appearance, so add it. If it is, skip it. When the loop finishes, uniqueValues holds every distinct value exactly once, in the order of its first appearance.

The cost is in the question. Searching an array means scanning it element by element, so the check takes time proportional to the size of uniqueValues, which can grow up to n. Doing that scan for each of the n values gives O(n^2). A later lesson replaces the array with a hash set to make the check fast; this one keeps the array, so you see why the set helps.

Step by step

Declare uniqueValues with let as an empty array of type number[]. It will hold each distinct value the first time it is met, and it is the answer at the end. Writing the type out keeps the element type precise: without it, TypeScript has nothing to infer it from.
Walk over the values. The indexes don't matter here, so use a for...of loop that gives each element directly, named value.
Check and add. Inside the loop, test !uniqueValues.includes(value) and, if it holds, call push(value). This ensures a value is stored only the first time it appears.
Return uniqueValues after the loop.

The solution in TypeScript

class Solution {
    removeDuplicates(nums: number[]): number[] {
        let uniqueValues: number[] = [];
        for (let value of nums) {
            if (!uniqueValues.includes(value)) {
                uniqueValues.push(value);
            }
        }
        return uniqueValues;
    }
}

Details worth knowing:

for...of against for...in. for (let value of nums) yields the elements. for (const i in nums) yields the indexes, and as strings: "0", "1", and so on. Mixing them up is a common source of bugs.
includes returns a boolean. It compares with the "same value zero" rule: it matches equal numbers, and unlike indexOf it also finds NaN. For example [NaN].includes(NaN) is true, while [NaN].indexOf(NaN) is -1.
The input stays untouched. The method only reads nums and returns a different array. The caller's array is as it was.
Compare numbers, not arrays. includes on an array of arrays compares by reference, so two arrays with the same contents count as different. That is not an issue here, because the elements are plain numbers.
The annotation is for the compiler. number[] is erased when the code is compiled. Pushing a string into uniqueValues would be reported by the compiler, but nothing checks this at run time.

Complexity

Time: O(n^2). The loop runs n times. Each includes call scans up to all of uniqueValues, which has at most n elements. In the worst case, when all values are distinct, the scans cost 0, 1, 2, ... up to n - 1 steps, about n^2 / 2 in total. When there are many repeats, uniqueValues stays short and the work is smaller, but the worst case sets the bound.

Space: O(n). In the worst case uniqueValues holds all n values.

Edge cases and common mistakes

Empty array. The loop doesn't run, and the method returns [].
All values equal. [5, 5, 5] gives [5].
No duplicates. The result has the same values as the input, in the same order.
Checking the wrong array. Testing whether nums includes value is always true, since the value came from nums. The test must be against uniqueValues.
Forgetting the !. Without the negation the method pushes only values that are already stored, so nothing is ever pushed and the result is empty.
Using the built-in sort() to prepare. If you try to sort first and compare neighbours, remember that sort() with no comparator sorts as text: [10, 9, 1] becomes [1, 10, 9].

Testing

[2, 3, 1, 1, 4, 3, -2, 1] gives [2, 3, 1, 4, -2].
[5, 5, 5] gives [5].
[] gives [].
[1, 2, 3] gives [1, 2, 3].

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free