Problem overview
The function guestsMissing receives two arrays 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 that changes nothing. The names in invited are all different.
For invited = ["Ava", "Leo", "Mia", "Zoe"] and arrived = ["Leo", "Zoe"], the answer is 2: Ava and Mia are still missing. For invited = ["Ava", "Leo"] and arrived = ["Leo", "Max", "Leo"], the answer is 1. Leo checked in twice but is one guest, and Max was never invited. For invited = ["Sam", "Kim"] and an empty arrived, the answer is 2.
Approach: start with everyone missing, cross names off
Counting arrivals directly goes wrong, because a repeated check-in or an uninvited guest would inflate the count. Turn the problem around instead. At the start, every invited guest is missing. Each arrival takes one name off the list of missing guests. What is left at the end is the answer.
A set fits this well. Building it from invited gives one entry per guest. Removing a name that is in the set shrinks it by one. Removing a name that isn't in it, such as an uninvited guest or a second check-in of someone already removed, does nothing. Both awkward cases are handled without any extra if.
Step by step
- Build the set of missing guests with
Set(invited), stored in avarnamedmissing, because names will be removed. - Loop over the arrivals with
for name in arrived. - Remove each name from
missing. For an unknown name or a repeat,removereturnsniland the set stays as it was. - Return
missing.countafter the loop. These are the invited guests who never checked in.
The solution in Swift
class Solution {
func guestsMissing(_ invited: [String], _ arrived: [String]) -> Int {
var missing = Set(invited)
for name in arrived {
missing.remove(name)
}
return missing.count
}
}
Two Swift details. First, remove returns the removed value as an optional, but it is marked so that the compiler doesn't warn when you ignore the result. Second, the parameters are unlabelled (_), so the function is called as guestsMissing(invited, arrived).
Watching the set shrink
Take the second example. The set starts with 2 names, Ava and Leo. The arrivals are then processed one at a time:
| Arrival | Names left in the set |
|---|---|
| Leo | 1 |
| Max | 1 |
| Leo | 1 |
The first Leo removes a name. Max is not in the set, and the second Leo is already gone, so neither changes the size. The function returns 1, for Ava.
Testing
On the three examples the function returns:
2
1
2
Common mistakes
- Returning
invited.count - arrived.count. For the second example this gives 2 - 3 = -1. Repeats and uninvited guests break the subtraction. - Counting arrivals that are in
invited. Without a set, Leo's second check-in would be counted again. The set removes a name only once. - Using
letformissing. Removing from a constant set is a compile error. - Worrying about an empty
arrived. The loop just doesn't run, and the answer is the number of invited guests.
