Start learning free

LESSON 243 OF 679 · SETS

Remove Repeats in Rust: Keep First Copies With a HashSet

Practice Read the full explanation

You get a Vec of integers nums. Some values may appear more than once.

Return a new Vec that has each value only once.

Keep the first copy of each value and drop the later ones. The values stay in the order they first appear in nums.

 

Example 1:

Input: nums = [3, 1, 3, 2, 1]
Output: [3, 1, 2]
Explanation: The second 3 and the second 1 are repeats.
They are dropped, and 3, 1 and 2 stay in their order.

Example 2:

Input: nums = [6, 6, 6, 6]
Output: [6]
Explanation: Only the first 6 stays.

Example 3:

Input: nums = [4, 9, 2]
Output: [4, 9, 2]
Explanation: No value repeats, so every number stays.

 

Constraints:

  • nums has at least one number.
  • Every number is between -109 and 109.
STEP 1 OF 7
    Ctrl + Enter to check

    RUST · SETS

    Remove Repeats in Rust, explained

    Problem overview

    The function remove_repeats receives a vector of integers nums, some of which may appear more than once. It returns a new vector in which each value appears once. The first copy of each value stays, later copies are dropped, and the values keep the order in which they first appear.

    For [3, 1, 3, 2, 1] the answer is [3, 1, 2]. For [6, 6, 6, 6] it is [6]. For [4, 9, 2], with no repeats, nothing changes.

    Approach

    Read the numbers from left to right and remember which ones you have already met. A number that is new goes into the result; a number you have met is skipped. A HashSet is the right memory: asking whether it contains a value is fast, so each number is judged at once.

    Why not just turn the vector into a set and back? A HashSet has no order. Collecting [3, 1, 3, 2, 1] into a set and back into a vector gives the right three values, but in an order that can differ from run to run, so the "order of first appearance" rule is lost. The set is only the memory here; the result vector keeps the order.

    Step by step

    1. Create an empty HashSet<i32> called seen, declared with let mut.
    2. Create an empty Vec<i32> called result, also let mut.
    3. Loop over &nums, left to right. Each num is a reference to a number.
    4. Check !seen.contains(num). The ! flips the answer, so the condition means "not met yet".
    5. Inside the if, push *num onto result. The star turns the reference into the number itself.
    6. Also insert *num into seen, so the next copy is recognised.
    7. After the loop, return result. Returning inside the loop would give back only the first value.

    The solution in Rust

    impl Solution {
    fn remove_repeats(nums: Vec<i32>) -> Vec<i32> {
        let mut seen: HashSet<i32> = HashSet::new();
        let mut result: Vec<i32> = Vec::new();
        for num in &nums {
            if !seen.contains(num) {
                result.push(*num);
                seen.insert(*num);
            }
        }
        return result;
    }
}

    seen.contains(num) takes num as it is, because contains wants a reference and num already is one. push and insert take the value itself, hence *num.

    Trying it

    [3, 1, 3, 2, 1]                ->  [3, 1, 2]
[6, 6, 6, 6]                   ->  [6]
[4, 9, 2]                      ->  [4, 9, 2]
[-5, -5, 0, -5, 1000000000]    ->  [-5, 0, 1000000000]

    Negative numbers and large values behave like any others. The values fit in i32, so no conversion is needed.

    Why the order of the two steps matters

    For each number the loop asks one question and does two things. The question comes first: "is it new?". Only then, if it is, does the number go into result and into seen. The two actions belong together: a number that is in result must also be in seen, or its next copy would be added again. Keeping them inside the same if guarantees that the two collections always agree.

    The vector keeps the order and the set keeps the memory. Each does the job it is good at: a vector remembers positions, and a set answers "have I seen this?" without scanning.

    Common mistakes

    • Using the set as the answer. The set loses the order. Collecting [3, 1, 3, 2, 1] into a set gives three values, but a set may list them in any order, so the result can't be trusted to match.
    • Forgetting to insert into seen. Then nothing is ever recognised as a repeat, and the result equals the input.
    • Inserting before checking. If a value is added to seen first, the check always says it was met, and nothing reaches the result.
    • Mixing up references. result.push(num) would push a reference into a Vec<i32> and fail to compile; use *num.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free