Ruby - Find element not in common for two arrays

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  resultend

As @iamnotmaynard noted in the comments, this is traditionally a set operation (called the symmetric difference). Ruby's Set class includes this operation, so the most idiomatic way to express it would be with a Set:

Set.new(a) ^ b

That should give O(n) performance (since a set membership test is constant-time).

a = [1, 2, 3]b = [2, 3, 4]a + b - (a & b)# => [1, 4]