Start learning free

LESSON 227 OF 414 · SORTING

Number of Distinct Values in Rust: 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 the value at index i has not been seen before. How can we check this?

The value at index i has never been seen before if it is different from the value at index i - 1.

STEP 1 OF 5
    Ctrl + Enter to check

    RUST · SORTING

    Distinct Values in Rust, explained

    Problem overview

    The function distinct_values receives a vector of integers, nums, and returns how many different values it contains. Each value counts once, however many times it appears.

    For nums = [1, 5, -3, 1, -4, 2, -4, 7, 7] the different values are 1, 5, -3, -4, 2 and 7, so the answer is 6. An empty vector gives 0.

    The lesson asks for O(n log n) time and O(1) extra space. That rules out a second collection for the values already seen, and it points toward sorting.

    Approach: sort, then count the changes

    The direct way to count distinct values is to compare each element with every earlier one, which is O(n^2). Sorting makes this much easier. Once the vector is in ascending order, equal values sit next to each other in one block. The example becomes:

    [-4, -4, -3, 1, 1, 2, 5, 7, 7]

    Now an element is a new value exactly when it differs from the element just before it. The first element is always new, so the count starts at 1, and each later position adds 1 when nums[i] != nums[i - 1]. In the sorted example the changes happen at -3, 1, 2, 5 and 7, five of them, and 1 + 5 gives 6.

    Sorting costs O(n log n) and the scan is a single pass of O(n), so sorting sets the total.

    This works because sorting groups equal values without needing to know them in advance. Sorting by itself never removes or changes anything, so the number of blocks of equal values in the sorted vector is the number of distinct values in the original. The scan only counts where one block ends and the next begins, and it never has to look further than the neighbour on the left.

    Step by step

    1. Handle the empty vector first. The starting code already returns 0 for it. Everything below can assume at least one element exists.
    2. Sort nums in place with sort(). The parameter is declared mut nums, so the function is allowed to reorder it. The call returns nothing.
    3. Start the count at 1. Declare distinct as a mutable i32, the function's return type. The first element is always a new value.
    4. Loop from the second element with i in 1..nums.len(), so every element has a left neighbour to compare with.
    5. Count each change. If nums[i] differs from nums[i - 1], add 1 with += 1, because Rust has no ++ operator.
    6. Return distinct as the last expression, with no semicolon.

    The solution in Rust

    impl Solution {
    fn distinct_values(mut nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        nums.sort();
        let mut distinct: i32 = 1;
        for i in 1..nums.len() {
            if nums[i] != nums[i - 1] {
                distinct += 1;
            }
        }
        distinct
    }
}

    The Rust details worth a closer look:

    • The early return matters. The loop reads nums[i - 1] and the count starts at 1. For an empty vector the count of 1 would be wrong, so the guard returns 0 before the rest runs.
    • 1..nums.len() is safe for any length. A range with start 1 and end 1 is empty, so a one-element vector skips the loop and keeps the count of 1. Because i starts at 1, i - 1 is never below zero, which matters since i is a usize.
    • sort() changes the vector in place. It returns (), so the next line uses nums itself. The vector was moved into the function, so the caller's copy is not affected.
    • Integer ordering. The default sort() orders i32 numerically, so negatives come first. Only equal values need to be adjacent for this algorithm, and any consistent order would give that.
    • The return type. The count is an i32 because the function says so. The length of a vector is a usize, so a count taken from nums.len() would need an as i32 cast.

    Complexity

    Time: O(n log n). The sort takes O(n log n). The loop makes one comparison per element, O(n).

    Space. The scan uses a few integers. The lesson treats the sort as in-place. Rust's stable sort() may allocate a temporary buffer, so strictly it can use O(n) extra, while sort_unstable() sorts without one and gives the same count here.

    Edge cases and common mistakes

    • Empty vector. Returns 0 through the guard.
    • One element. The loop doesn't run and the answer is 1.
    • All values equal. For [4, 4, 4] no neighbours differ, so the answer is 1.
    • Counting without sorting. Comparing neighbours in the unsorted vector counts changes between neighbours, not distinct values. In [1, 2, 1] that would give 3, while the answer is 2.
    • Starting the count at 0. This misses the first value of every block, and the result is too small by one.
    • Counting equal neighbours. Adding 1 when nums[i] == nums[i - 1] counts the duplicates instead of the distinct values.

    Testing

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