2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Careful, on average it is $O(n)$. $\endgroup$ – vonbrand Feb 23 '16 at 13:50
  • $\begingroup$ Isn't also the amortized worst case $O(n)$? $\endgroup$ – erensezener Feb 23 '16 at 15:12
0
$\begingroup$

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

You might not be able to do better than this in the general case.

If the arrays are sorted we will be able to do it in linear time, by traversing one array in the ascending order and other in the descending order. There is no need to actually reverse one of the arrays.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.