Algorithm to find added/removed elements in an array

Question

I am looking for the most efficent way of solving the following

Problem:

given an array Before = { 8, 7, 2, 1} and an array After ={1, 3, 8, 8}
find the added and the removed elements

the solution is:
        added = 3, 8 
        removed = 7, 2

My idea so far is:

for i = 0 .. B.Lenghtt-1
{
    for j= 0 .. A.Lenght-1
    {
        if A[j] == B[i]

            A[j] = 0;
            B[i] = 0;

            break;
    }
}

// B elemnts different from 0 are the Removed elements
// A elemnts different from 0 are the Added elemnts

Does anyone know a better solution perhaps more efficent and that doesn't overwrite the original arrays

Answer 1

Sorting is your friend.

Sort the two arrays (a and b), and then walk them (using x and y as counters). Move down both 1 at a time. You can derive all your tests from there:

• if a[x] < b[y], then a[x] was removed (and only increment x)
• if a[x] > b[y], then b[y] was added (and only increment y)

(I may have missed an edge case, but you get the general idea.)

(edit: the primary edge case that isn't covered here is handling when you reach the end of one of the arrays before the other, but it's not hard to figure out. :)

Answer 2

You could also use a Dictionary<int, int> and a algorithm similar to this:

foreach i in source_list: dictionary[i]++;
foreach i in dest_list: dictionary[i]--;

The final dictionary tells you which elements were inserted/removed (and how often). This solution should be quite fast even for bigger lists - faster than sorting.

Answer 3

if your language as multiset available (set with count of elements) your question is a standard operation.

B = multiset(Before)
A = multiset(After)

result is A.symdiff(B) (symdiff is union minus intersection and that is exactly what you are looking for to have removed and added).

Obviously you can also get removed only or added only using classical difference between sets.

It can trivially be implemented using hashes and it's O(n) (using sort is slightly less efficient as it is O(n.log(n)) because of the sort itself).