LESSON 241 OF 677 · SETS

Only in the First in Scala: Set Difference Keeping Order

You get two ArrayBuffers of integers, a and b.

Return a new ArrayBuffer with the values of a that are not in b.

Each value goes into the result only once. Keep the values in the order they first appear in a.

If every value of a is also in b, return an empty ArrayBuffer.

Example 1:

Input: a = [1, 2, 3, 4], b = [2, 4]
Output: [1, 3]
Explanation: 2 and 4 are in b, so they are left out.

Example 2:

Input: a = [5, 6, 5, 7], b = [7]
Output: [5, 6]
Explanation: 7 is in b.
5 appears twice in a, but only once in the result.

Example 3:

Input: a = [1, 2], b = [2, 3, 1]
Output: []
Explanation: Both values of a are also in b, so nothing is left.

Constraints:

a and b each have at least one number.
Every number is between -10⁹ and 10⁹.

STEP 1 OF 8

Guided

Ctrl + Enter to check

Only In First in Scala, explained

Problem overview

The method onlyInFirst gets two ArrayBuffer[Int] values, a and b, and returns a new buffer with the values of a that are not in b. Each value appears once in the result, and the values keep the order in which they first appear 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 answer is [1, 3]. For a = [5, 6, 5, 7] and b = [7] it 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] it is empty.

Approach

Two questions are asked about every number of a: is it in b, and is it already in the result? A set answers each quickly. A set of the values of b handles the first question, and a second set of values already placed in the result handles the second. Reading a from left to right keeps the order.

Step by step

Build setB, a mutable set of the values of b. Repeats in b collapse into one.
Create an empty set seen for the values already put in the result.
Create an empty ArrayBuffer[Int] called result.
Loop over a with for (num <- a).
Inside, require both !setB.contains(num) and !seen.contains(num), joined with &&: b does not have the number and the result does not have it yet.
If both hold, append the number to result and add it to seen.
After the loop, return result.

The solution in Scala

class Solution {
    def onlyInFirst(a: ArrayBuffer[Int], b: ArrayBuffer[Int]): ArrayBuffer[Int] = {
        val setB = scala.collection.mutable.Set[Int](b.toSeq: _*)
        val seen = scala.collection.mutable.Set[Int]()
        val result = ArrayBuffer[Int]()
        for (num <- a) {
            if (!setB.contains(num) && !seen.contains(num)) {
                result += num
                seen += num
            }
        }
        return result
    }
}

The set built from b makes each check fast. Looking through b for every number of a would work, but it would scan b again and again.

Why two sets

The set setB never changes after it is built. It describes b. The set seen grows as the result grows, and it only describes the result. Keeping them apart keeps each check simple: one asks "does b have it?", the other "did I already keep it?". Putting the values of a into setB would mix the two questions and give wrong answers.

Testing

On the three examples the method returns 1 3, 5 6 and an empty buffer (the tests print lists as values separated by spaces).

Another way

The same result comes from a filter and distinct:

val bs = ArrayBuffer(7).toSet
val result = ArrayBuffer(5, 6, 5, 7).filterNot(bs).distinct

For a = [5, 6, 5, 7] and b = [7] this gives ArrayBuffer(5, 6). A Set can be used as a function that answers "is it in here?", which is what filterNot needs.

Edge cases and common mistakes

Forgetting seen. Without it, [5, 6, 5, 7] against [7] would return 5 6 5.
Using || instead of &&. The number must pass both checks.
Swapping the roles of a and b. The loop goes over a, the set holds b.
Using set subtraction alone. a.toSet -- b gives the right values, but a set gives no promise about the order, and the result must follow the order of a. Your loop keeps that order.
Returning null for the empty case. The result is simply an empty buffer, which the loop produces when nothing is added.

Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free