Given two arrays A1,A2, return if for a given X , there is a pair of ai∈Ai such that a1+a2=X ((n log()))

Question

The question is fairly easy to understand, the problem is i need the algorithm running time to be (n log()), which i couldn't achieve.

Given two arrays with positive integers,lets call them A1,A2 return if for a given X(the input) , there is a pair of ai∈Ai such that a1+a2=X.

For example A1 = { 22,4,5 } A2 = { 11,3,9 } For X = 7 we return true, since 3+4=7 (4 its our a1, and 3 its our a2).

Thanks.

Answer 1

Sort both arrays, in $O(n\ln n)$.
You have two pointers. One points to the first number in $A_1$, and the other starts at the last number in $A_2$.
Repeat:
If the sum is less than $X$, move the first pointer to the next number in $A_1$. If the sum is greater, move the second pointer to the previous number in $A_2$.
If there is a solution, then the first pointer will, at some time, point to the right number in $A_1$. The second pointer will then come down to the right number in $A_2$.
The first pointer won't pass the right number in $A_1$ before the right number in $A_2$ is reached, and vice versa.