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

(a-b) | (b-a) # => [3] See ruby-doc.org/core-1.9.3/Array.html#method-i-2D and note that it's not commutative, i.e. in general a-b != b-a — Reinstate Monica -- notmaynard
– Reinstate Monica -- notmaynard, Commented Nov 25, 2013 at 22:55
@ShawnBalestracci Right you are. I had even written it correctly in my test console, but rewrote it wrong. — Reinstate Monica -- notmaynard
– Reinstate Monica -- notmaynard, Commented Nov 25, 2013 at 22:57
Or sort the arrays (which should be O(n log n)), then iterate through the two, adding elements which are in only one array to a result array (O(n)). — Reinstate Monica -- notmaynard
– Reinstate Monica -- notmaynard, Commented Nov 25, 2013 at 23:10

Reinstate Monica -- notmaynard · Accepted Answer · 2013-11-26 16:29:33Z

32

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

edited Nov 26, 2013 at 16:29

answered Nov 25, 2013 at 23:31

Reinstate Monica -- notmaynard

5,4892 gold badges29 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

BuffMcBigHuge Over a year ago

Union of the difference! Thanks for that! Using underscore: result = _.union(_.difference(a, b), _.difference(b, a));

Chuck · Accepted Answer · 2013-11-25 23:26:55Z

26

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).

edited Nov 25, 2013 at 23:26

answered Nov 25, 2013 at 23:19

Chuck

238k31 gold badges306 silver badges392 bronze badges

Comments

sawa · Accepted Answer · 2013-11-25 23:14:31Z

11

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

edited Nov 25, 2013 at 23:14

answered Nov 25, 2013 at 23:09

sawa

169k51 gold badges287 silver badges398 bronze badges

2 Comments

Donato Over a year ago

Which one is preferrable? This or the accepted solution?

Anatoly Over a year ago

this solution is better from garbage collection point of view (you can see less value for total_allocated_object with disabled GC).

ChrisF · Accepted Answer · 2020-02-26 16:36:31Z

1

The solution for Array divergences is like:

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

You can also read my blog post about Array coherences

edited Feb 26, 2020 at 16:36

ChrisF

138k31 gold badges265 silver badges335 bronze badges

answered Oct 25, 2016 at 18:58

Christian Rolle

1,69413 silver badges13 bronze badges

Collectives™ on Stack Overflow

Ruby - Find element not in common for two arrays

4 Answers 4

1 Comment

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related