Sort one of the array using nlogn algorithm (merge sort or heap sort) and then take an element from second array perform binary search in the sorted array if you find it store it in your result array. Complexity: nlogn for sorting the array with n elements, and logn for each lookup you do and since you it m times (which is the number of elements in array 2) it becomes mlogn. So the final complexity will be nlogn + mlogn == log(n) * (m + n).