Problem overview
onlyInFirst receives two slices of integers, a and b, and returns a new slice 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 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] nothing is left.
Approach
The question about each value of a is "is it in b?". Asking that of a slice means scanning it every time. A set answers it directly, so the first job is to put the values of b into a set. Repeats in b collapse into one entry, which is fine.
The second job is the same as removing repeats: a second set, seen, records which values already went into the result, so a repeated value of a is added only once. Reading a from left to right keeps the order of first appearance.
Go has no set type, so both sets are map[int]bool.
Step by step
- Create
setB := map[int]bool{}and fill it with a loop overb, settingsetB[num] = true. Go can't build the map from a slice in one expression. - Create
seen := map[int]bool{}andresult := []int{}. - Loop over
ain order. - If the value is not in
setBand not inseen, append it toresultand mark it inseen. - Return
resultafter the loop.
The solution in Go
func onlyInFirst(a []int, b []int) []int {
setB := map[int]bool{}
for _, num := range b {
setB[num] = true
}
seen := map[int]bool{}
result := []int{}
for _, num := range a {
if !setB[num] && !seen[num] {
result = append(result, num)
seen[num] = true
}
}
return result
}
Both conditions use the fact that a missing key reads as false, so !setB[num] means "not in b". The two checks are joined with && because both must hold.
The result starts as []int{}, not nil, so when nothing is left you get an empty slice, as the statement asks.
The two sets answer two different questions, so neither can replace the other. setB never changes after it is filled: it says what b contains. seen changes as the loop runs: it says what has already been put in the result. In the second example, a = [5, 6, 5, 7] and b = [7]: 5 is not in setB and not yet in seen, so it is added; 6 likewise; the second 5 is in seen, so it is skipped; 7 is in setB, so it is skipped.
Testing
a = [1 2 3 4], b = [2 4] -> [1 3]
a = [5 6 5 7], b = [7] -> [5 6]
a = [1 2], b = [2 3 1] -> []
The values in b can be negative or very large, up to a billion in size. That causes no trouble: a map key is any int, and the sets store only the values that actually appear, not a slot for every possible number.
Common mistakes
- Skipping the
seenset. Witha = [5, 6, 5, 7]the result would be[5 6 5]. - Looping over a map to build the result. Map order is random in Go, so the order of
awould be lost. - Using
||instead of&&. A value would then be added when it is missing from either set, which lets values ofbthrough. - Swapping
aandb. The result holds the values ofa, so the set is made fromb.
