Efficient algorithm for finding optimal sum from both arrays

Question

I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See examples below. What is the efficient way to find the solution for this?

eg1: 
A =[200,300,600,900]
B =[1000,200,300,500]
M = 900
Output : A(2), B(2)
600 from A and 300 from B sums 900.

eg1: 
A =[200,300,600,1000]
B =[1000,400,600]
M = 1500
Output : A(3), B(1)
1000 from A and 400 from B sums 1400 which is near to the sum 1500.

Answer 1

So rewriting my answer from the comments.

Let $n$ be the size of the input (say the total size of both arrays), then $\Omega(n \log n)$ is a reasonable lower-bound on the running time of the problem. (See this paper for a similar bound).

One way to solve it is hence to sort both arrays and then using sliding window technique (two pointers) to find two elements, one from each array, with the largest sum less than or equal to $M$. The total running time of this algorithm is $O(n \log n + m \log m + n + m)$, where the sliding window technique runs in linear time getting a total running time of $O(n\log n + m \log m)$ for $n$ the size of the first array and $m$ the size of the second one.

A slightly better solution is to sort only the smaller among the two arrays, and for each element in the other array, look up the largest element in the first array such that the sum of both elements is less than or equal to the $M$. Assuming $n \leq m$, we can get a running time of the form $O((n+m)\log n)$ using binary search for the look-ups.

Answer 2

There are three ways how you could proceed:

If both arrays are already sorted for example in ascending order, then you start at the beginning of the first array and the end of the last array; if the sum is too small you skip to the next element of the first array, if the sum is too large you skip to the previous element of the second array, and so on.

If one array only is sorted, then you try each element x of the other array, lookup the element closest to M - x using binary search, and use the best pair.

If neither array is sorted, you sort either one or both. Calculate the runtime of either approach; it seems best to sort the smaller array, which then takes O (n log m) where m is the size of the larger array, and m the size of the smaller array.

If the larger array is already sorted, sorting the smaller array as well may be faster, because the sorting is done in O (m log m), and the first method takes only linear time. And if the arrays are of comparable size (say $m = n^{1/2}$) so log m vs. log n doesn't affect asymptotic behaviour, then what is fastest on some implementation will depend on the actual implementation.