myabe you should use a third array and just push to it all the entries of arr1 as long as they don't appear in arr2 (you can use a hash for that purpose). It's n complexity at the most.

Hotshot