LESSON 241 OF 348 · HASH TABLE

Number of Distinct Values in TypeScript: O(n) with a Set

Given an array of integers, count how many distinct values exist in the array.

Example:

Input: [1, 5, -3, 1, -4, 2, -4, 7, 7]
Output: 6
Explanation: the distinct values in the array are [1, 5, -3, -4, 2, 7]

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 6

Guided

Ctrl + Enter to check

TYPESCRIPT · HASH TABLE

Distinct Values in TypeScript, explained

Problem overview

The method distinctValues receives an array of integers, nums, and returns how many different values it contains. Repeats count once.

For [1, 5, -3, 1, -4, 2, -4, 7, 7] the distinct values are 1, 5, -3, -4, 2, 7, so the answer is 6. The array has nine elements, but 1, -4 and 7 each appear twice.

Approach: remember what you have seen

The statement asks for O(n) time and O(n) extra space. A slower route is to compare every element with every earlier one, which costs O(n²). Another is to sort the array and count the places where neighbouring values differ, which costs O(n log n). Both avoid extra memory, and the statement allows extra memory in exchange for speed.

A hash set gives you that speed. Walk through the array once. For each number, ask the set whether it has been seen. If not, this is the first copy: add it to the set and count it. If so, skip it. Checking and adding are both O(1) on average, so the whole walk is O(n).

On the example, the walk meets 1, 5, -3 (three new values, count 3), then 1 again (skipped), -4 and 2 (count 5), -4 again (skipped), 7 (count 6) and the second 7 (skipped).

Step by step

Create the set. values is a new Set<number>(). The type argument matters: an empty new Set() would give the compiler nothing to infer from.
Create the counter. answer starts at 0, which is also the right result for an empty array.
Loop with for...of. value is declared with const because it is never reassigned inside the loop body.
Test for a first sighting. !values.has(value) is true only for a number the set has not stored yet.
Record it and count it. Adding to the set is what makes later copies get skipped; incrementing answer counts this copy.
Return answer.

The solution in TypeScript

class Solution {
    distinctValues(nums: number[]): number {
        let values = new Set<number>();
        let answer = 0;
        for (const value of nums) {
            if (!values.has(value)) {
                values.add(value);
                answer++;
            }
        }
        return answer;
    }
}

A few TypeScript details:

Set<number> is erased. The type argument only helps the compiler. After compiling, it is a plain Set.
for...of gives values, not indices. for...in over an array gives index strings, which is a classic slip.
Numbers compare by value. 0 and -0 count as one value in a set, and so do two NaNs.
A shorter form exists. new Set(nums).size gives the same answer. The explicit loop shows what the set is doing for you.

The set at each step

Following the loop on the example, the set grows only when a number is new. The set always holds exactly the numbers counted so far, which is why answer and values.size are always equal. That is the invariant to keep in mind: every number is counted once, at the moment it enters the set, and never again, because from then on has finds it.

value  new?  set afterwards          answer
1      yes    {1}                    1
5      yes    {1, 5}                 2
-3     yes    {1, 5, -3}             3
1      no     {1, 5, -3}             3
-4     yes    {1, 5, -3, -4}         4
2      yes    {1, 5, -3, -4, 2}      5
-4     no     {1, 5, -3, -4, 2}      5
7      yes    {1, 5, -3, -4, 2, 7}   6
7      no     {1, 5, -3, -4, 2, 7}   6

Because the set already holds the count in size, the separate answer variable is a convenience for the lesson rather than a necessity. Returning values.size at the end would work equally well.

Compared with the slower ways

The two alternatives from the approach section are worth seeing, because they show what the set saves you. Checking against a list of earlier values with includes scans that list every time:

function viaIncludes(nums: number[]): number {
    const seen: number[] = [];
    for (const v of nums) {
        if (!seen.includes(v)) seen.push(v);
    }
    return seen.length;
}

It returns 6 on the example, but each includes call is O(n), so the total is O(n²). The sorting version runs in O(n log n):

function viaSort(nums: number[]): number {
    if (nums.length === 0) return 0;
    const sorted = [...nums].sort((a, b) => a - b);
    let count = 1;
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] !== sorted[i - 1]) count++;
    }
    return count;
}

It also returns 6. Two details matter here. The comparator (a, b) => a - b is required: without it, sort() compares numbers as strings, and [10, 9, 1, 10] would come out as [1, 10, 10, 9]. And the copy [...nums] keeps the caller's array unchanged, because sort works in place.

Complexity

Time: O(n). The loop runs once per element, and each iteration does one has and at most one add, both constant time on average.

Space: O(n). In the worst case, when all values differ, the set holds n numbers.

Edge cases and common mistakes

Large inputs. The set grows with the number of distinct values, so an array with a million different numbers needs a set of a million entries. That is the extra O(n) space the statement allows.
Empty array. The loop never runs and the method returns 0.
All equal. [4, 4, 4] gives 1.
All different. [1, 2, 3] gives 3.
Counting before checking. Incrementing answer outside the if counts every element, so the result is just nums.length.
Adding before checking. If you call values.add(value) first and test has afterwards, every value looks like a repeat of itself and the count is 0.
Mixing up the loop forms. for (const value in nums) would give the index strings "0", "1" and so on, and the method would count positions instead of values. Use of.
Treating the set as a list. A set has size, not length, so values.length is undefined and the compiler reports it.
Negative numbers. They need no special handling. A set stores -3 as readily as 3.

Testing

[1, 5, -3, 1, -4, 2, -4, 7, 7] gives 6.
[] gives 0.
[0, -0] gives 1.
[2, 2, 2] gives 1.
[-1, 1, -1, 1] gives 2, since -1 and 1 are different values.

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

Start learning free