Problem overview
The method guestsMissing gets two ArrayBuffer[String] lists, invited and arrived, and returns how many invited guests have not arrived yet. A guest may check in more than once and still counts as one guest. A person who was not invited may check in too, and that changes nothing.
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"] the answer is 1: Leo checked in twice but is one guest, and Max was never invited. With invited = ["Sam", "Kim"] and nobody arrived, the answer is 2.
Approach
Start by assuming everyone invited is missing, then cross off each name that arrives. The names left at the end are the missing guests. A set suits this because taking a name out of a set that does not contain it does nothing. Both awkward cases, a guest who checks in twice and a stranger, are then handled without any extra checks.
Step by step
- Build a mutable set
missingfrominvited. The names ininvitedare all different, so the set starts with every invited guest. - Loop over the arrivals with
for (name <- arrived). - Inside the loop, remove the name with
-=. A stranger is not in the set, and a guest seen twice is gone after the first time, so-=does nothing in both cases. - After the loop, return
missing.size.
The solution in Scala
class Solution {
def guestsMissing(invited: ArrayBuffer[String], arrived: ArrayBuffer[String]): Int = {
val missing = scala.collection.mutable.Set[String](invited.toSeq: _*)
for (name <- arrived) {
missing -= name
}
return missing.size
}
}
The set is mutable, so -= changes it in place, and val missing is fine because the name always refers to the same set. invited.toSeq: _* passes the buffer's names to the set one by one.
Why a set and not a buffer
With an ArrayBuffer, -= removes only the first matching value, and a missing name would need its own check. A set holds each name once, so a repeated check-in is harmless, and a name that is not there is ignored. The loop body is a single line.
Testing
On the three examples, the method returns 2, 1 and 2. An empty arrived buffer is fine: the loop does not run, and the answer is the size of the invited list.
Another way
Scala can subtract one collection from another when both are sets:
val missingCount = (invited.toSet -- arrived).size
For invited = ["Ava", "Leo"] and arrived = ["Leo", "Max", "Leo"] this is 1, like the loop. The loop version shows the idea step by step, which is the point of this lesson.
Edge cases and common mistakes
- Subtracting the sizes.
invited.size - arrived.sizegives -1 for the second example, because it counts the repeated Leo and the stranger Max. - Checking the stranger first. There is no need for an
ifaround-=; a name that is not in the set is skipped by itself. - Looping over the wrong list. The loop goes over the arrivals, and the set holds the invited names, not the other way round.
- Returning the set instead of its size. The method returns an
Int.
