Problem overview
The function remove_duplicates receives a vector of integers and returns a new vector with each value appearing once. The result may be in any order. For [2, 3, 1, 1, 4, 3, -2, 1] the result holds 2, 3, 1, 4 and -2, in any arrangement.
The lesson asks for O(n) time and O(n) extra space.
Approach: let a set do the work
A set holds each value at most once, so pouring the numbers into a set removes the duplicates. Adding to a hash set takes O(1) on average, so filling it from n numbers takes O(n). Comparing every element with every other one would take O(n²), and sorting first would take O(n log n).
The price is order. A hash set doesn't remember where values came from and iterates in an arbitrary order, so the result can differ from the input's first-appearance order. The statement allows any order, so this is fine.
The solution has two moves: collect the vector into a HashSet, then collect the set back into a vector.
Step by step
- Build the set.
nums.into_iter().collect()feeds every number into aHashSet<i32>. The annotation onuniquetellscollect()which collection to build; without it the compiler can't choose. - Turn the set back into a vector.
unique.into_iter().collect()is the last expression of the function. Here no annotation is written, because the return typeVec<i32>tellscollect()what to build.
The solution in Rust
use std::collections::HashSet;
impl Solution {
fn remove_duplicates(nums: Vec<i32>) -> Vec<i32> {
let unique: HashSet<i32> = nums.into_iter().collect();
unique.into_iter().collect()
}
}
Rust details:
into_iter()consumes. It takes ownership ofnumsand moves each number out, sonumscan't be used afterwards. That is fine, since the function owns the vector and doesn't need it again. To keep the original, usenums.iter().copied().collect()instead.collect()is generic. It can build aVec, aHashSet, aStringand more. The target type comes from an annotation on the variable or from the function's return type.- No semicolon on the last line. The expression is the function's return value.
- Arbitrary order. The order of the output may differ between runs of the program, which is why a test of this function should compare sorted results or sets.
Complexity
Time: O(n). Building the set visits each number once, with O(1) average work per insertion. Converting the set back to a vector visits each of its at most n elements once.
Space: O(n). The set and the result vector each hold up to n values.
Edge cases and common mistakes
- Empty vector. The set is empty and the function returns an empty vector.
- All equal.
[5, 5, 5]returns[5]. - Expecting the original order. A hash set doesn't keep it. If the first-appearance order mattered, you'd loop over the vector, keep a set of seen values and push each new value onto a result vector as it appears.
- Missing annotation.
let unique = nums.into_iter().collect();doesn't compile, because the compiler can't tell which collection is wanted. - Using a vector after
into_iter(). The vector was moved and the compiler rejects any later use.
Testing
[2, 3, 1, 1, 4, 3, -2, 1]gives the values -2, 1, 2, 3 and 4 (five values, any order).[]gives[].[5, 5, 5, 5]gives[5].
