Compare two arrays or arraylists, find similar and different values

Question

I have two arrays (or arraylists if it is easier) of strings. I need to compare these, find which only exist in the first array, which exist in both, and which only exist in the second array. These arrays are different lengths, and may be in different orders. If necessary, I suppose I could sort them...

I know I could hack this together, but I think this might have a fairly standard and efficient / "best" solution, and I am curious more than anything.

I am using c# for this, but if you want to write your solution in another language, any help is welcome.

Thanks for the help!

Answer 1

If the arrays are large then you'll want to use a data structure that is efficient for these operations; arrays are not.

The naive solution is O(n^2) in time if the arrays are of size n.

If you sort the arrays in place then you can binary search them for the items; sorting will likely be O(n lg n) and searching n times at a cost of lg n per search will also be O(n lg n) in time.

If you turn each array into a HashSet<T> first then you can do it in O(n) time and O(n) extra space.

Answer 2

var onlyinfirst = from s in list1 where !list2.Contains(s) select s;
var onlyinsecond = from s in list2 where !list1.Contains(s) select s;
var onboth = from s in list1 where list2.Contains(s) select s;