Extract elements from one list that aren't in another

Question

Simply, I have two lists and I need to extract the new elements added to one of them. I have the following

val x = List(1,2,3)
val y = List(1,2,4)

val existing :List[Int]= x.map(xInstance => {
      if (!y.exists(yInstance =>
        yInstance == xInstance))
        xInstance
    })

Result :existing: List[AnyVal] = List((), (), 3)

I need to remove all other elements except the numbers with the minimum cost.

Answer 1

Pick a suitable data structure, and life becomes a lot easier.

scala> x.toSet -- y
res1: scala.collection.immutable.Set[Int] = Set(3)

Also beware that:

if (condition) expr1

Is shorthand for:

if (condition) expr1 else ()

Using the result of this, which will usually have the static type Any or AnyVal is almost always an error. It's only appropriate for side-effects:

if (condition) buffer += 1
if (condition) sys.error("boom!")

Answer 2

retronym's solution is okay IF you don't have repeated elements that and you don't care about the order. However you don't indicate that this is so.

Hence it's probably going to be most efficient to convert y to a set (not x). We'll only need to traverse the list once and will have fast O(log(n)) access to the set.

All you need is

x filterNot y.toSet
// res1: List[Int] = List(3)

edit:

also, there's a built-in method that is even easier:

x diff y

(I had a look at the implementation; it looks pretty efficient, using a HashMap to count ocurrences.)