LESSON 241 OF 677 · SETS

Only in the First List in Kotlin: Two HashSets

You get two ArrayLists of integers, a and b.

Return a new ArrayList 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 ArrayList.

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 Kotlin, explained

Problem overview

The function onlyInFirst gets two lists of integers, a and b. It returns a new list with the values of a that are not in b. Each value goes into the result once, and the values stay in the order 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], the answer is [5, 6]: 7 is in b, and 5 appears twice in a but only once in the result. For a = [1, 2] and b = [2, 3, 1], the result is empty.

Approach

There are two questions to ask about each number in a: is it in b, and is it already in the result? A list answers each by scanning, which gets slow for long lists. A HashSet answers by a fast lookup. So use two sets: one built from b, and one that collects the values already put in the result.

Walking through a from left to right keeps the order. A number goes into the result only if both questions get the answer no.

Step by step

Build a set from b with b.toHashSet(), in a val named setB. Repeats in b collapse into one, which does not matter here.
Create an empty set seen with hashSetOf<Int>(). It remembers what is already in the result, so a repeated value in a is not added twice.
Create an empty mutableListOf<Int>() named result.
Loop over a with the variable num.
Inside, an if with two checks joined by &&: !setB.contains(num) and !seen.contains(num). Both must be true.
Inside the if, add num to result and to seen.
After the loop, return result.

The solution in Kotlin

class Solution {
    fun onlyInFirst(a: List<Int>, b: List<Int>): List<Int> {
        val setB = b.toHashSet()
        val seen = hashSetOf<Int>()
        val result = mutableListOf<Int>()
        for (num in a) {
            if (!setB.contains(num) && !seen.contains(num)) {
                result.add(num)
                seen.add(num)
            }
        }
        return result
    }
}

The && operator stops as soon as its left side is false, so when num is in b the second check is never made. The tests print lists as values separated by spaces. The three examples give:

1 3
5 6

For the third example the result is empty, so nothing is printed for it.

Two more inputs worth trying: a = [-5, 3, -5, 8] with b = [3, 3, 9] gives -5 8 (negative numbers work the same, the repeat in b does no harm, and -5 appears once). And a = [7, 7] with b = [7] gives an empty list, whose size is 0. When no value of a is in b, such as a = [4] with b = [1, 2], the result is 4.

Another way

A library call can express the filter: listOf(5, 6, 5, 7).filter { it !in setOf(7) } gives [5, 6, 5]. It drops the values found in the second collection, but it keeps the repeated 5. This lesson asks for each value once, which is why the extra seen set is there.

Complexity

Building setB takes one step per element of b, and the loop takes one step per element of a, each with fast lookups. The two sets and the result use extra space.

Common mistakes

Leaving out seen. The input [5, 6, 5, 7] would then give 5 6 5.
Searching b as a list for every number. It works, but it scans b each time.
Using || instead of &&. The number must pass both checks, not one of them.
Returning the set seen. It does not keep the order of a.

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

Start learning free