What if there are repetitions in either of the arrays? And the OP asked for a efficient solution: while I have not tested your algorithm, and it is potentially interesting for being linear in the sizes of the arrays, I believe that building a hash and then iterating over its keys will make it slow enough for many reasonable data sets. (I don't think this would matter, but the OP is convinced it does...)