Ruby - Find element not in common for two arrays

Question

I've been thinking about a following problem - there are two arrays, and I need to find elements not common for them both, for example:

a = [1,2,3,4]
b = [1,2,4]

And the expected answer is [3].

So far I've been doing it like this:

a.select { |elem| !b.include?(elem) }

But it gives me O(N ** 2) time complexity. I'm sure it can be done faster ;)

Also, I've been thinking about getting it somehow like this (using some method opposite to & which gives common elements of 2 arrays):

a !& b  #=> doesn't work of course

Another way might be to add two arrays and find the unique element with some method similar to uniq, so that:

[1,1,2,2,3,4,4].some_method #=> would return 3

Answer 1

The simplest (in terms of using only the arrays already in place and stock array methods, anyway) solution is the union of the differences:

a = [1,2,3,4]
b = [1,2,4]
(a-b) | (b-a)
=> [3]

This may or may not be better than O(n**2). There are other options which are likely to give better peformance (see other answers/comments).

Edit: Here's a quick-ish implementation of the sort-and-iterate approach (this assumes no array has repeated elements; otherwise it will need to be modified depending on what behavior is wanted in that case). If anyone can come up with a shorter way to do it, I'd be interested. The limiting factor is the sort used. I assume Ruby uses some sort of Quicksort, so complexity averages O(n log n) with possible worst-case of O(n**2); if the arrays are already sorted, then of course the two calls to sort can be removed and it will run in O(n).

def diff a, b
  a = a.sort
  b = b.sort
  result = []
  bi = 0
  ai = 0
  while (ai < a.size && bi < b.size)
    if a[ai] == b[bi]
      ai += 1
      bi += 1
    elsif a[ai]<b[bi]
      result << a[ai]
      ai += 1
    else
      result << b[bi]
      bi += 1
    end
  end
  result += a[ai, a.size-ai] if ai<a.size
  result += b[bi, b.size-bi] if bi<b.size
  result
end