Problem overview
The method guestsMissing receives two lists of names, invited and arrived, and returns how many invited guests haven't arrived yet. A guest may check in more than once and still counts as one guest. Someone who wasn't invited may check in too, and they don't change the answer.
For invited = ["Ava", "Leo", "Mia", "Zoe"] and arrived = ["Leo", "Zoe"], Ava and Mia are still missing, so the answer is 2. For invited = ["Ava", "Leo"] and arrived = ["Leo", "Max", "Leo"], Leo checked in twice but is one guest, and Max wasn't invited, so only Ava is missing and the answer is 1. If nobody has arrived, every invited guest is missing: 2 for ["Sam", "Kim"].
Approach
Start by assuming that every invited guest is missing. Each arrival then takes one name off the missing guests. What is left at the end is the answer.
A HashSet fits this well because of how remove behaves. Removing a name that is not in the set does nothing, so an uninvited guest is harmless. Removing a name a second time also does nothing, so a guest who checks in twice is taken off once. The two tricky cases in the statement need no special code.
Step by step
- Build a
HashSet<String>namedmissingfrominvited. - Loop over
arrived, with aStringnamedname. - Inside the loop, call
removeonmissingwithname. - After the loop, return
missing.size().
The solution in Java
class Solution {
public int guestsMissing(List<String> invited, List<String> arrived) {
HashSet<String> missing = new HashSet<>(invited);
for (String name : arrived) {
missing.remove(name);
}
return missing.size();
}
}The method takes List<String>, so it accepts an ArrayList or any other list. new HashSet<>(invited) copies the names into a new set and leaves the list itself untouched. The return value of remove (a boolean) is ignored, since the code doesn't need to know whether the name was there.
Here is the first example in motion. The set starts as Ava, Leo, Mia and Zoe. The arrival Leo takes Leo off, leaving three names. The arrival Zoe takes Zoe off, leaving two: Ava and Mia. The loop ends, and missing.size() is 2. In the second example, the first Leo removes him, Max isn't in the set so nothing changes, and the second Leo is a no-op too. Only Ava remains.
Edge cases and common mistakes
- Counting arrivals. Subtracting
arrived.size()frominvited.size()gives wrong answers when a guest checks in twice or an uninvited person arrives. For the second example it would give 2 - 3 = -1. - Removing from the list. A list's
removewith a name only takes the first match and costs a scan. The set avoids both problems. - An empty
arrived. The loop doesn't run, and the answer is the number of invited guests.
Why a set, not a list
You could keep the missing names in an ArrayList instead. It would work for small inputs, but a list's remove(name) has to scan the names one by one to find the match, and it removes only the first copy. A set finds the name directly and holds each name once, so the repeated check-ins and the uninvited guests are handled by the data structure rather than by extra if statements.
Testing
Running the solution on the three examples gives:
2
1
2