Problem overview
The function only_in_first receives two vectors of integers, a and b. It returns a new vector with the values of a that are not in b. Each value goes into the result once, in the order it first appears in a. If every value of a is also in b, the result is empty.
For a = [1, 2, 3, 4] and b = [2, 4] the answer is [1, 3]. For a = [5, 6, 5, 7] and b = [7] it is [5, 6]: 7 is in b, and 5 appears twice in a but once in the result. For a = [1, 2] and b = [2, 3, 1] the result is [].
Approach
Two questions are asked about every number of a: does b have it, and is it already in the result? Both are membership questions, and a HashSet answers them quickly. Put the values of b in one set (set_b), and keep the values already placed in the result in a second set (seen). Then walk through a from left to right and keep a number only when it fails both checks. Walking in order keeps the order of first appearance.
Step by step
- Build
set_bfrombwithb.into_iter().collect(). Repeats inbcollapse into one entry. - Create an empty
seenset withHashSet::new(), aslet mut. - Create an empty
resultvector, aslet mut. - Loop over
&a. - Test
!set_b.contains(num) && !seen.contains(num): not inb, and not in the result yet. Both must hold, so the checks are joined with&&. - Inside the
if, push*numontoresultand insert*numintoseen. - After the loop, return
result, which may be empty.
The solution in Rust
impl Solution {
fn only_in_first(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let set_b: HashSet<i32> = b.into_iter().collect();
let mut seen: HashSet<i32> = HashSet::new();
let mut result: Vec<i32> = Vec::new();
for num in &a {
if !set_b.contains(num) && !seen.contains(num) {
result.push(*num);
seen.insert(*num);
}
}
return result;
}
}
set_b is never changed, so it is declared without mut. b.into_iter() consumes b, which is fine because b isn't needed afterwards. The loop borrows a with &a instead, so each num is a reference; contains takes it as it is, and push and insert take *num.
Trying it
a = [1, 2, 3, 4], b = [2, 4] -> [1, 3]
a = [5, 6, 5, 7], b = [7] -> [5, 6]
a = [1, 2], b = [2, 3, 1] -> []
a = [3, 3, 3], b = [1] -> [3]
Why two sets
The two sets answer two different questions, and neither can replace the other. set_b is fixed from the start: it never changes during the loop. seen grows as the loop runs, and describes the result so far. You could instead check result.contains(num), but that scans the result for each number, while the set answers at once.
If you read the task as "remove from a everything that b has", the second set is the part that is easy to forget. The task also asks for each value once, so a value that appears twice in a still needs the memory of what has already been kept.
Common mistakes
- Leaving out
seen. With only the check againstb, the second example would give[5, 6, 5]. - Using
||instead of&&. A number would be kept if it is missing frombor new to the result, which lets in values thatbhas. - Looping over the wrong vector. The result must follow the order of
a, so the loop goes overa, not overbor a set. - Searching
bas a vector.b.contains(num)works but scansbfor each number; a set answers at once.
