Jacka - 6 months ago 32

Ruby 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)`

Also, I've been thinking about getting it somehow like this (using some method opposite to

`&`

`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`

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

Answer

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
```