Exclude all innocents from suspects (set difference)
You are given two slices of ints, suspects and innocents, each sorted ascending. Return a new slice containing every value of suspects that is not present in innocents, keeping the original order.
Requirement: O(n+m) time. Do not mutate the inputs.
Examples:
suspects=[1,2,3,4,5],innocents=[2,4]→[1,3,5]suspects=[3,80,123,421,936],innocents=[80,936]→[3,123,421]
func filter(suspects, innocents []int) []int {
// your code here
return nil
}Write the implementation.
Build a map[int]struct{} set from innocents (the zero-size value means membership only, no payload). Range suspects, appending each value whose comma-ok lookup is absent from the set — O(n+m) time, O(m) space. Because both inputs are sorted, a two-pointer merge is an O(1)-space alternative.
- ✗Scanning
innocentsper suspect and calling it O(n) instead of O(n·m) - ✗Mutating
suspectsin place withappend, corrupting the caller's slice - ✗Building the set from
suspects, which loses the original order and any duplicates
- →Both inputs are sorted — how would a two-pointer merge cut the extra space to O(1)?
- →Why prefer
map[int]struct{}overmap[int]boolfor a membership set?
Task
Return the suspects values absent from innocents, preserving order.
func filter(suspects, innocents []int) []int {
skip := make(map[int]struct{}, len(innocents)) // membership set
for _, v := range innocents {
skip[v] = struct{}{}
}
result := make([]int, 0, len(suspects))
for _, v := range suspects {
if _, innocent := skip[v]; innocent {
continue
}
result = append(result, v)
}
return result
}How it works
First collect innocents into a map[int]struct{} set. struct{} takes zero bytes — the idiomatic way to say "I only care that the key exists, not its value".
Then one pass over suspects: if a value is in the set (comma-ok _, innocent := skip[v]), skip it, otherwise append it to result. Each element is processed once with an O(1) lookup, so the total is O(n+m) time and O(m) extra space.
Why result = append(result, v): append returns a new slice header (which may point at a reallocated backing array once capacity is exhausted), so its result must be assigned back. Pre-sizing with make([]int, 0, len(suspects)) avoids repeated reallocations. The input slices are never mutated.
⚠️ The input is sorted, so a two-pointer alternative runs in O(1) extra space — it builds no set and walks both slices in lockstep.
