Problem overview
The function intersection receives two vectors of integers, first and second, and returns a vector with the numbers that appear in both. Each number appears once in the result, however often it occurs in the inputs, and the result is sorted in ascending order. The values lie between -1000 and 1000, and each vector has between 1 and 1000 elements.
For first = [1, 2, 2, 1] and second = [2, 2] the answer is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the answer is [4, 9]: both numbers are in both vectors, and the repeats in second are collapsed into one.
The lesson asks for O(n + m) time, plus the time to sort the shared numbers, where n and m are the two lengths.
Approach: remember one array in a set
The slow way checks every number of one vector against every number of the other, which costs O(n * m). The faster way relies on a HashSet, which answers "is this number in here?" in O(1) on average and stores each number once.
Put every number of the first vector in a set. Then go through the second vector, and for each number that the first set contains, put it in a second set, the answer set. Both sets drop duplicates by themselves, so the repeated 2s in the first example, or the repeated 9s and 4s in the second, collapse without any extra code.
Sets have no order, so the last move is to copy the answer set into a vector and sort it. That final sort is the extra cost the lesson's note mentions: it is proportional to the number of shared values, not to the full input sizes.
Step by step
- Rename the inputs to
nums1andnums2. Theletbindings move the vectors into the new names, with no copying. - Create the set
seenas an emptyHashSet<i32>, declaredmut. It will hold the numbers ofnums1. - Loop over
&nums1with the variablei. Looping over the reference borrows the elements, soiis a&i32andnums1stays usable. - Insert each number with
seen.insert(*i). The*reads the number behind the reference. Inserting a number that's already in the set changes nothing. - Create the answer set,
intersection_set, another emptymutHashSet<i32>. - Loop over
&nums2the same way. - Test membership. If
seen.contains(i)holds, insert*iinto the answer set. Thecontainsmethod takes a reference, soigoes in as it is, whileinserttakes the number itself. - Convert the answer set to a vector named
resultusinginto_iter().collect(). The type annotationVec<i32>selects the target ofcollect(). - Sort the vector with
sort()and return it as the last expression.
The solution in Rust
use std::collections::HashSet;
impl Solution {
fn intersection(first: Vec<i32>, second: Vec<i32>) -> Vec<i32> {
let nums1 = first;
let nums2 = second;
let mut seen: HashSet<i32> = HashSet::new();
for i in &nums1 {
seen.insert(*i);
}
let mut intersection_set: HashSet<i32> = HashSet::new();
for i in &nums2 {
if seen.contains(i) {
intersection_set.insert(*i);
}
}
let mut result: Vec<i32> = intersection_set.into_iter().collect();
result.sort();
result
}
}
On the two examples it returns [2] and [4, 9].
The Rust details worth a closer look:
use std::collections::HashSet;is needed becauseHashSetisn't part of the prelude.- References in
for i in &nums1. Iterating over a&Vec<i32>yields&i32. That is why the code writes*ito insert andcontains(i)to look up. insertreturns abool. It istrueif the number was new andfalseif the set already had it. The lesson ignores the result, as a statement, and the set still ends up correct.- Sets are unordered. The iteration order of a
HashSetis unspecified and can differ between runs, so the finalsort()isn't optional. Without it the right numbers can come out in the wrong order. into_iter()consumes the set. It moves the numbers out into the vector, sointersection_setcan't be used afterwards. That is fine here, because nothing needs it.- The last line has no semicolon. A bare
resultis the value the function returns.
Another valid route: sort and dedup() each vector, then walk both with two indices. It needs no hash set but costs O(n log n + m log m).
Complexity
Time: O(n + m) plus the final sort. Filling seen takes n insertions, scanning second takes m lookups, and each operation is O(1) on average. If r numbers are shared, sorting them adds O(r log r).
Space: O(n + m). seen holds up to n numbers and the answer set up to min(n, m). The result vector has at most min(n, m) elements.
Edge cases and common mistakes
- No shared numbers.
[1, 2, 3]and[4, 5, 6]give an empty vector,[]. - Duplicates in either input. The sets collapse them, so each shared number appears once.
- Negative numbers.
[-5, 0, 7]and[7, -5, -5, 0]give[-5, 0, 7]. Negative values sort before zero and the positives, as expected. - Forgetting to sort. The result may contain the right numbers in an arbitrary order, and the lesson's tests expect ascending order.
- Collecting from
nums2directly. Pushing each matching number ofsecondinto the result without a set would list9twice for the second example. The answer set is what makes the numbers unique. - Dereferencing mistakes. Writing
seen.insert(i)withia&i32is a type error, since the set holdsi32values andinsertwants one.
Testing
first = [1, 2, 2, 1],second = [2, 2]gives[2].first = [4, 9, 5],second = [9, 4, 9, 8, 4]gives[4, 9].first = [1, 2, 3],second = [4, 5, 6]gives[].first = [-5, 0, 7],second = [7, -5, -5, 0]gives[-5, 0, 7].first = [3],second = [3]gives[3].
