Problem overview
The method onlyInFirst receives two lists of integers, a and b. It returns a new list with the values of a that are not in b. Each value appears in the result once, in the order it first appears in a. If every value of a is also in b, the result is an empty list.
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 only once in the result. For a = [1, 2] and b = [2, 3, 1] the answer is [].
Approach
Two questions are asked about every value of a: is it in b, and is it already in the result? Both are "is this value there?" questions, so both are best answered by sets.
setB = set(b)turnsbinto a set. Repeats inbcollapse, and each check is fast.seenholds the values already put in the result, so a later copy of the same value is skipped.- A list
resultcollects the answer in order, because sets do not keep order.
Step by step
- Build
setB = set(b). - Create an empty set
seen = set(). - Create an empty list
result = []. - Loop with
for num in a. Readingafrom left to right gives the order the task wants. - Test
num not in setB and num not in seen: both must hold. - Inside the test, append
numtoresult. - Also add
numtoseen. - After the loop, return
result.
The solution in Python
class Solution:
def onlyInFirst(self, a: List[int], b: List[int]) -> List[int]:
setB = set(b)
seen = set()
result = []
for num in a:
if num not in setB and num not in seen:
result.append(num)
seen.add(num)
return resultThe condition reads as two checks joined by and. For a = [5, 6, 5, 7] and b = [7], the first 5 passes both checks and is stored. The 6 does too. The second 5 fails the second check, since 5 is in seen. The 7 fails the first check. The result is [5, 6].
When nothing passes, result is still [], which is the right answer.
Why two sets
The two sets answer different questions, and mixing them up is the usual stumble. setB never changes after it is built: it is a fixed picture of b. seen grows while the loop runs: it is a picture of the result so far. A value is kept only when it is absent from the first picture and from the second. Checking membership in a set takes about the same time whether it holds ten values or ten thousand, whereas checking a list means looking at each value in turn, so with sets the work grows in step with the lengths of the two lists, not with their product.
Why not a one-line comprehension
A comprehension such as [x for x in a if x not in setB] removes the values in b, but keeps repeats: for [5, 6, 5, 7] and [7] it gives [5, 6, 5]. The seen set is what enforces "each value once".
Edge cases
Repeats in b are harmless: the set keeps one copy of each. Negative numbers and zero are ordinary values. If a and b hold exactly the same values, the loop never appends anything and the method returns an empty list. Values that appear in b but not in a never matter, because the loop only reads a.
Testing
| a | b | result |
|---|---|---|
[1, 2, 3, 4] | [2, 4] | [1, 3] |
[5, 6, 5, 7] | [7] | [5, 6] |
[1, 2] | [2, 3, 1] | [] |
Common mistakes
- Testing
num not in bwith the list. It works, but walks throughbfor every value ofa. The set makes each check fast. - Skipping
seen. Repeats inathen repeat in the result. - Joining the checks with
or. A value would be kept if either check passed, so values frombwould slip through. - Using set subtraction alone.
set(a) - set(b)has the right values, but no promised order.
