Write an Array extension that removes every element that appears in a second array. What is the complexity, and what if the elements are only Equatable?

29.1.3 · L2 · Interview

Reported at: Meta

Predict first

What does the extension print for the four calls?

extension Array where Element: Hashable {
    func removingAll(of other: [Element]) -> [Element] {
        let drop = Set(other)                        // O(m) once, then O(1) per element
        return filter { !drop.contains($0) }
    }
    mutating func removeAll(of other: [Element]) {
        let drop = Set(other)
        removeAll { drop.contains($0) }
    }
}
extension Array where Element: Equatable {           // no Hashable? fall back to O(n*m)
    func removingAllSlow(of other: [Element]) -> [Element] { filter { !other.contains($0) } }
}
print([1, 2, 2, 3, 4, 5].removingAll(of: [2, 5]))
var names = ["ann", "bo", "cy", "bo"]
names.removeAll(of: ["bo"])
print(names)
print([1, 2, 3].removingAll(of: []))
print([Box(1), Box(2)].removingAllSlow(of: [Box(2)]).count)
struct Box: Equatable { let v: Double; init(_ v: Double) { self.v = v } }
  • [1, 3, 4] / ["ann", "cy"] / [1, 2, 3] / 1
  • [1, 2, 3, 4] / ["ann", "bo", "cy"] / [] / 1
  • [1, 3, 4] / ["ann", "cy"] / [] / 2

Mental model. A bouncer with a printed banned-list: turning the list into a quick lookup sheet once is far cheaper than reading the whole list for every guest.

The naive version calls other.contains($0) inside filter: O(n × m). When Element: Hashable, build a Set(other) once (O(m)) and filter with O(1) lookups: O(n + m), as the extension shows. Offer both shapes the standard library uses: a non-mutating removingAll(of:) that returns a new array, and a mutating one built on removeAll(where:), which edits in place in a single pass without O(n²) repeated shifting. Constrain the extension with where Element: Hashable; elements that are only Equatable need the slow contains fallback in a second extension, because Swift cannot hash them.

Say what duplicates do: every occurrence of a listed value is removed (the output keeps the order of the survivors), and removing an empty list is a no-op. Mention that Array.remove(at:) in a loop is O(n) each time, so a manual loop with removals is O(n²) and easy to get wrong while indices shift. Reported at Meta (anonymous, unverified); it tests generic constraints and complexity at once.

Listed values disappear in every position, the survivors keep their order, an empty list removes nothing, and the Equatable fallback also works.

Common traps

  • Removing from the array while looping over its indices. The indices shift; use removeAll(where:).
  • Forgetting the Hashable constraint, so Set(other) does not compile for the generic element.

They might follow up with

  • What if order does not matter? Convert both to sets and use subtracting, but duplicates and order are lost.
  • Is there something like this in the standard library? removeAll(where:) and filter; the set difference is on Set.

Related questions

  • 29.1.1 Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get…
  • 29.2.2 Implement a hash map from scratch (get, set, remove), then extend it: what do you test and how does resizing…
  • 29.1.2 Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. How do you do it…

← Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes…   Add two non-negative numbers given as decimal strings, without… →