[Java] Find pair of values from two arrays that sum up closer to given target

Given two arrays, not necessarily of same length, find a pair of values with one value from each array whose sum is closest to a given target.

Example

1, 2, 3

3, 1, 4

target = 5, we return (2,3) or (1,4)

target = 10 we return (3,4)

The simple O(NM) solution without using extra space, is simply to compute all sums and track the closest to our target.

Luckily we have just seen how to find a value in a sorted matrix, and a key insight to solving this problem is recognizing we can process our input to end up in the scenario from the other problem.

If we sort the arrays in O(NlogN + OMlogM) time, we can then apply the algorithm from before and find a solution in O(N+M) time. The overall runtime would therefore be O(NlogN + OMlogM) time and O(N+M) space assuming for example we are using mergesort on both arrays.

To avoid creating the matrix though (would be O(NM) time), we can just use pointers and consider one array as the rows and the other as the columns, then calculate only the sums we need while walking around of fictional matrix.

By tracking the best pair and delta from target seen so far, we will eventually reach our solution.

You can check my implementation of findClosestPairSumUpToK on my Gist along with some tests in ClosestPairSumUpToKJTests.