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!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Careful, on average it is $O(n)$. $\endgroup$
    – vonbrand
    Commented Feb 23, 2016 at 13:50
  • $\begingroup$ Isn't also the amortized worst case $O(n)$? $\endgroup$
    – erensezener
    Commented Feb 23, 2016 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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