algorithm - Efficient method to find what elements of Array A are in Array B -

in particle case need javascript code find strings of array in array b.

but it's more interesting ask general question:

given array a length of n , array b, return boolean[] array of length n such boolean[i] true iff a[i] item in b.

what efficient solution problem? both of array unsorted , array b can empty , can larger or smaller array a.

there few different ways varying complexities.

first, nested loop on both lists , print out elements a when find corresponding solution in b. o(ab) time , o(1) space.

second, sort both lists , walk through lists in lockstep looking matches (imagine merge operation in mergesort). o(aloga + blogb) time , either o(1) or o(a+b) space, depending on whether want sort in-place or not.

third, sort second list , binary search elements in 1 @ time. o(blogb + alogb) time , o(1) or o(b) space, again depending on whether sort in-place or not.

the tosters proposed solution whereby create hash set , repeated queries on it. depending on how hash set resolves collisions, asymptotically equivalent in worst case either first or third solutions (the underlying buckets can lists or binary search trees).