Problem overview
The method onlyInFirst receives two arrays of integers, a and b, and returns a new array with the values of a that are not in b. Each value goes into the result once, 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 an empty array.
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 only once in the result. For a = [1, 2] and b = [2, 3, 1] nothing is left, so the result is [].
Approach: two sets, one loop
Each value of a has to pass two tests: b must not contain it, and the result must not contain it yet. Both are "is this value there?" questions, and a Set answers them quickly.
- A set built from
b, calledsetB, answers the first test. Repeats inbcollapse into one entry, which is fine, since only membership matters. - A second set,
seen, records the values already put in the result. It answers the second test, and it is the same idea that removes repeats from a single array.
Looping over a from left to right keeps the first-appearance order. The values go into an array, result, because the answer has to be an array.
Step by step
- Build
setBwithnew Set(b), typedSet<number>. - Create an empty
seenset of numbers. - Create an empty
resultarray of numbers. - Loop over
awithfor...of. - Test both conditions with
&&:!setB.has(num)and!seen.has(num). The body runs only when both are true. - Push
numontoresult. - Add
numtoseen, so that a later copy inais skipped. - Return
resultafter the loop. It may be empty.
The solution in TypeScript
class Solution {
onlyInFirst(a: number[], b: number[]): number[] {
let setB: Set<number> = new Set(b);
let seen: Set<number> = new Set();
let result: number[] = [];
for (let num of a) {
if (!setB.has(num) && !seen.has(num)) {
result.push(num);
seen.add(num);
}
}
return result;
}
}
Notes on the code:
- Short-circuit
&&. If the first test is false, the second is not evaluated. That makes no difference to the answer here, only to how much work is done. - The inputs are not changed. The method builds new containers and leaves
aandbas they were.
Another way
The same result can come from removing repeats first and filtering afterwards:
function onlyInFirst(a: number[], b: number[]): number[] {
const setB: Set<number> = new Set(b);
return [...new Set(a)].filter((num) => !setB.has(num));
}
On the three examples it returns [1,3], [5,6] and []. new Set(a) drops the repeats of a while keeping first-appearance order, and filter keeps the values that b does not have. The lesson's loop does the same work in one pass and shows each idea separately.
Edge cases and common mistakes
- Forgetting
seen. Filtering with only the first test,a.filter(n => !setB.has(n)), keeps repeats. For[5, 6, 5, 7]and[7]it returns[5,6,5], not[5,6]. - Repeats of a value that is not in
b.a = [2, 2, 9]withb = [2]gives[9]. Every 2 is excluded byb, however many times it appears. - Searching
bas an array.b.includes(num)works, but it scansbfor every value ofa. A set avoids that. - Swapping the arrays. The values of
bthat are missing fromado not matter. The set is built fromb, and the loop runs overa. - Value types. The sets compare values with exact equality, so the number 1 and the string
"1"are different. With the typed arrays of this lesson that cannot arise.
Testing
a = [1, 2, 3, 4],b = [2, 4]gives[1, 3].a = [5, 6, 5, 7],b = [7]gives[5, 6].a = [1, 2],b = [2, 3, 1]gives[].a = [2, 2, 9],b = [2]gives[9].
