Start learning free

LESSON 267 OF 414 · HASH TABLE

Distinct Values in Rust: O(n) with a HashSet

Practice O(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:

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


STEP 1 OF 6
    Ctrl + Enter to check

    RUST · HASH TABLE

    Distinct Values in Rust, explained

    Problem overview

    The function distinct_values receives a vector of integers and returns how many different values it contains. For [1, 5, -3, 1, -4, 2, -4, 7, 7] the distinct values are 1, 5, -3, -4, 2 and 7, so the answer is 6. The lesson asks for O(n) time and O(n) extra space.

    Approach: ask a set whether you have seen the value

    One way to count distinct values is to sort the vector and count the places where neighbouring values differ. That costs O(n log n) for the sort. To get to O(n), trade memory for speed: remember every value you have seen in a hash set, where checking and adding take O(1) on average.

    The loop looks at each number once. If the number is new, it is counted. If the set already holds it, it is a repeat and is skipped. In Rust, HashSet::insert does the check and the addition in one call: it returns true when the value was not in the set and false when it already was. So the result of insert is exactly the test "is this value new?".

    On [4, 4, 9]: the first 4 is inserted (true, count 1), the second 4 is rejected (false), and 9 is inserted (true, count 2). The answer is 2.

    Step by step

    1. Create the set values with let mut and HashSet::new(). It must be mut because inserting changes it. The element type is not written: the compiler infers it from the later insert(*value).
    2. Create the counter answer as an i32 set to 0. The function returns an i32.
    3. Loop over &nums with the variable value. Borrowing the vector means each value is a &i32.
    4. Insert and test in one step. values.insert(*value) needs the number itself, so the reference is dereferenced with *.
    5. Count the new value by adding 1 to answer inside the if.
    6. Return answer as the last expression, without a semicolon.

    The solution in Rust

    impl Solution {
    fn distinct_values(nums: Vec<i32>) -> i32 {
        let mut values = std::collections::HashSet::new();
        let mut answer: i32 = 0;
        for value in &nums {
            if values.insert(*value) {
                answer += 1;
            }
        }
        answer
    }
}

    Rust details:

    • The full path. The set is written as std::collections::HashSet::new(), so no use line is needed. Adding use std::collections::HashSet; and writing HashSet::new() is the usual style.
    • Borrowing. for value in &nums only borrows the vector. Without the & the loop would take ownership and consume it.
    • Dereferencing. Since value is a &i32, *value is the number. Inserting the reference itself would build a set of references and change the inferred type.
    • The condition is a side effect. The insert call both changes the set and produces the bool, so it must be called exactly once per element.

    The loop could also be replaced by building a set from the vector and taking its length, as in nums.into_iter().collect::<HashSet<i32>>().len(), and that has the same complexity.

    Complexity

    Time: O(n). The loop makes one pass over the n numbers and each insert takes O(1) on average.

    Space: O(n). When every value is different, the set holds all n of them. This is the price for avoiding the sort.

    Edge cases and common mistakes

    • Empty vector. The loop does not run and the function returns 0.
    • All values equal. [4, 4, 4] gives 1.
    • Negative numbers and zero. They are ordinary keys: [0, -1, 0, -1] gives 2.
    • Counting twice. Calling contains and then insert works but does two hash lookups per element. The single insert is shorter and faster.
    • Returning the set's length with the wrong type. len() is a usize, so returning it from a function declared to give an i32 needs as i32. Counting in an i32 avoids the cast.

    Testing

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