# 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!

• 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)$.