Problem overview
The function onlyInFirst receives two arrays of integers, a and b. It returns a new array 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 result is [1, 3]. For a = [5, 6, 5, 7] and b = [7] the result 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 sets, one loop
The function does two checks on each value of a: is it missing from b, and is it new to the result? Both are "is this value in a group?" questions, and a set answers them fast.
- A set of
b's values, built once, answers the first. Repeats inbcollapse into one entry, which is fine. - A set of the values already put in the result answers the second.
Swift's sets also have a method for this kind of subtraction, subtracting. It returns a set, though, and a set has no order, so it can't give the first-appearance order the lesson asks for. The loop over a in order is what keeps the order.
Step by step
- Make
setBwithlet setB = Set(b). It never changes, soletis right. - Create
seen, an emptySet<Int>()withvar. It records the values already in the result. - Create
result, an empty[Int]withvar. - Loop over
afrom left to right. - Test both conditions with
&&:!setB.contains(num)and!seen.contains(num). Both must hold. - Append to
resultinside theif. - Insert into
seen, so a later copy of the same value is skipped. - Return
resultafter the loop. It can be empty.
The solution in Swift
class Solution {
func onlyInFirst(_ a: [Int], _ b: [Int]) -> [Int] {
let setB = Set(b)
var seen = Set<Int>()
var result = [Int]()
for num in a {
if !setB.contains(num) && !seen.contains(num) {
result.append(num)
seen.insert(num)
}
}
return result
}
}
In Swift, && stops as soon as the left side is false, so seen.contains(num) is only checked for values that aren't in b. Without setB, you would call b.contains(num) on an array, which walks through b every time.
Watching the loop
On a = [5, 6, 5, 7] with b = [7], the result grows like this:
| Number | Result afterwards |
|---|---|
| 5 | [5] |
| 6 | [5, 6] |
| 5 | [5, 6] |
| 7 | [5, 6] |
The second 5 is blocked by seen, and the 7 is blocked by setB.
Testing
The three examples give:
[1, 3]
[5, 6]
[]
Why not a one-liner
Two shorter forms exist, and each fails one of the rules. For a = [5, 6, 5, 7, 2] and b = [7], Set(a).subtracting(b) has the right 3 values, but sorting them gives [2, 5, 6], not the first-appearance order [5, 6, 2]. And a.filter { !Set(b).contains($0) } keeps the order but also the repeat, giving [5, 6, 5, 2]. The loop with two sets satisfies both rules at once.
Edge cases
Repeats in b cost nothing, because Set(b) keeps each value once: a = [4, -2, 4, 9] with b = [9, 9, 9] gives [4, -2]. Negative values work like any other. When b shares nothing with a, the result is a without its repeats, so [3, 3] with [8] gives [3].
Common mistakes
- Skipping
seen. Then[5, 6, 5, 7]with[7]would give[5, 6, 5]. - Using
a.filterwithb.containsalone. The order is right, but repeats fromastay in the result. - Returning
Array(Set(a).subtracting(b)). The values are right, but the order is not guaranteed. - Swapping the arrays. The result holds values of
athat are missing fromb, not the other way around.
