# Determine if there are 2 integers in 2 separate arrays add up to a given number

If I'm given 2 unsorted arrays A and B of n distinct integers and an integer z, how can I determine if there exists an integer in A and an integer in B that add up to z with an expected run time of O(n)?

I'm pretty sure that I would have to use a hash table(s) of some sort since I'm dealing with expected run time but I'm not sure how the algorithm would work.

Any help would be really appreciated! Thanks!

Insert the elements of the first array into a hashset S by subtracting from z. I.e., if 3 is an element of the first array, instert z - 3 into S. Then for each element in the second array, check if z - element is already in S. This procedure is O(n).
• Careful, on average it is $O(n)$. – vonbrand Feb 23 '16 at 13:50
• Isn't also the amortized worst case $O(n)$? – erensezener Feb 23 '16 at 15:12
Your best bet will be to sort the arrays one in ascending order and other in descending order and then do a linear scan. The complexity of the algorithm will be $O(n \log n)$.