Problem overview
The function guests_missing receives two vectors of names, invited and arrived, and returns how many invited guests haven't arrived yet. Two details shape the answer:
- A guest may check in more than once, but still counts as one guest.
- Someone who wasn't invited may check in, and that must not change the answer.
For invited = ["Ava", "Leo", "Mia", "Zoe"] and arrived = ["Leo", "Zoe"] the answer is 2 (Ava and Mia). For invited = ["Ava", "Leo"] and arrived = ["Leo", "Max", "Leo"] the answer is 1: Leo checked in twice, Max wasn't invited, only Ava is missing.
Approach
Start by assuming every invited guest is missing, then cross names off as people arrive. A HashSet fits: it holds each name once and removing a name that isn't in it does nothing. That one behaviour handles both tricky cases. A second check-in finds the name already gone, and an uninvited guest was never in the set. When the arrivals are done, whatever is left in the set is the answer.
Step by step
- Build the set
missingfrominvitedwithinto_iter().collect(). It must belet mut, because names will be removed. - Loop over
&arrived. Eachnameis a reference to aString. - Call
missing.remove(name). Sincenamealready is a reference, that is exactly whatremovewants. - After the loop, return
missing.len(). A length is ausize, so convert it withas i32to match the return type.
The solution in Rust
impl Solution {
fn guests_missing(invited: Vec<String>, arrived: Vec<String>) -> i32 {
let mut missing: HashSet<String> = invited.into_iter().collect();
for name in &arrived {
missing.remove(name);
}
return missing.len() as i32;
}
}
The result of remove (a bool) is simply ignored; the loop only cares about the effect.
Trying it
Running the function gives:
invited = [Ava, Leo, Mia, Zoe], arrived = [Leo, Zoe] -> 2
invited = [Ava, Leo], arrived = [Leo, Max, Leo] -> 1
invited = [Sam, Kim], arrived = [] -> 2
invited = [Sam], arrived = [Sam, Sam] -> 0
The third line is the case of an empty arrived: the loop never runs, so every invited guest is still missing. In the last line the second Sam removes nothing, and the answer stays 0 instead of going negative.
Why a set and not a vector
The same idea works with a vector: look up each arrival in invited and mark it. But a vector's contains and remove must scan from the start, and removing from the middle shifts every later element. A set finds a name directly, and removing a name that isn't there is not an error. That is why the loop in the solution has no if at all: the set absorbs the repeats and the uninvited names by itself.
The names in invited are all different, so building the set loses nothing. If the list could repeat a name, the set would count that guest once, which is also what a head count of guests should do.
Common mistakes
- Subtracting lengths.
invited.len() - arrived.len()counts check-ins, not guests: repeats and uninvited people throw it off. With["Ava", "Leo"]and["Leo", "Max", "Leo"]the difference is negative, and since lengths areusize, it wraps to a huge number in an optimized build instead of giving -1. - Counting inside the loop. Adding 1 per arrival counts repeats; the set does the de-duplication for you.
- Forgetting
mut. A set declared with plainletcan't have names removed. - Returning
missing.len()without the cast. The function returnsi32, and Rust does not convertusizetoi32by itself.
