Efficient algorithm for finding optimal sum from both arrays

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.

• stackoverflow.com/q/11928091/781723 – D.W. Oct 18 at 2:38
• Are the arrays sorted? – xskxzr Oct 18 at 4:52
• @xskxzr from the example you can verify the array is not sorted. – Marcelo Fornet Oct 18 at 5:57
• @D.W. this is arguably a different question in the sense that it asks for the greater value less than or equal to $M$ (and the array is not sorted). Anyway after sorting, the same solution to the other problems works here. – Marcelo Fornet Oct 18 at 5:59
• @narekBojikian this is good. Better than what i was thinking. – Zeus Oct 19 at 5:02

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.

• Theta(n log n) is not a reasonable lower bound - if one array has size 1, then the solution is much faster. – gnasher729 Oct 20 at 0:11
• You might want to check what lower-bound means. You can not say it is not tight because there is a case where you can solve the problem more efficiently. I am giving a lower-bound on the general case wich is supposed to span all instances of the problem (among which both $n$ and $m$ are big enough and $n = \Theta(m)$). – narek Bojikian Oct 20 at 12:10

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.