Start learning free

LESSON 201 OF 348 · SORTING

Number of Distinct Values in TypeScript: O(n log n) with Sorting

Practice O(n log n) Read the full explanation

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:

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


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another.

Then, we can traverse the sorted array from left to right using an index i. We should increment the solution if value nums[i] has not been seen before. How can we check this?

nums[i] has never been seen before if nums[i] != nums[i - 1].

STEP 1 OF 5
    Ctrl + Enter to check

    TYPESCRIPT · SORTING

    Distinct Values in TypeScript, explained

    Problem overview

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

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

    The statement sets a budget of O(n log n) time and O(1) extra space. A Set would be shorter, but it needs O(n) extra space. Here the idea is to get duplicates next to each other by sorting.

    Approach: sort, then count the changes

    The slow way is to compare each element with every element before it, which takes O(n²) time. Sorting makes that unnecessary. After sorting in ascending order, all copies of a value sit in one block. Within the sorted array, a value is new exactly when it differs from the element just before it.

    For the example, the sorted array is [-4, -4, -3, 1, 1, 2, 5, 7, 7]. Walking left to right, the value changes at -3, at 1, at 2, at 5 and at 7. The first element starts the first block, so the count is 1 plus 5 changes, which is 6.

    Step by step

    1. Sort nums in ascending order with the comparator (a, b) => a - b. Without the comparator, numbers are compared as strings and 10 would come before 9; equal values would still be adjacent, but a numeric sort is the safe habit.
    2. Start distinct at 1. The first element is always a new value, so the count begins at 1.
    3. Loop from index 1. Starting at the second element lets each element be compared with the one before it.
    4. Compare with the neighbour. If nums[i] differs from nums[i - 1], a new block starts, so add 1 to distinct.
    5. Return distinct after the loop.

    The solution in TypeScript

    class Solution {
    distinctValues(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let distinct = 1;
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                distinct++;
            }
        }
        return distinct;
    }
}

    Details worth knowing:

    • let in the loop header. let i limits the variable to the loop. The counter distinct is declared with let too, because it changes.
    • != and !==. Both work for two numbers. In TypeScript, comparing values of the same type, !== is the usual habit because it never converts types; the lesson's code uses != and gets the same result here.
    • Sorting changes the input. The caller's array ends up sorted. Copy it with [...nums] first if the original order matters.
    • The sort is the expensive part. The loop adds distinct++ at most n - 1 times.

    Complexity

    Time: O(n log n). Sorting takes O(n log n) and the loop is one pass of O(n), so sorting dominates.

    Space: O(1). The code adds only the counter and the loop index, and the sort works in place.

    Edge cases and common mistakes

    • All values equal. [2, 2, 2] never enters the if, so the answer stays 1.
    • A single element. [4] skips the loop and returns 1.
    • An empty array. This code returns 1, not 0, because the counter starts at 1. The lesson's inputs have at least one element; if an empty input were possible, a check at the top would be needed.
    • Forgetting the comparator. Default string order still keeps equal numbers together, so this particular count stays right. It is still a bad habit, because the same call gives the wrong order whenever numeric order matters.
    • Starting the loop at 0. Then nums[i - 1] reads nums[-1], which is undefined, so the first element would be counted twice.
    • Counting the equal pairs instead. Adding 1 when values match gives the number of duplicates, not the number of distinct values.

    Testing

    • [1, 5, -3, 1, -4, 2, -4, 7, 7] gives 6.
    • [10, 9, 9, 100] gives 3.
    • [2, 2, 2] gives 1.
    • [4] gives 1.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free