Find the pair(s) with the max sum with given constraints

Question

I was recently asked in a job interview to find the max sum across two arrays with given constraints. The question was phrased differently, but it boiled down to what I said above. Nothing was said about the elements being distinct, or the arrays being sorted.

Example:

A = [2000, 3000, 4000, 5000]
B = [6000, 5000, 4000, 1000]
Constraint: A[i] + B[j] <= 7000
Expected Result: (A[0], B[1]), (A[1], B[2])

Note that this isn't the same question as Find the pair across 2 arrays with kth largest sum because of the constraint.

A brute force solution is to take the cartesian product of the 2 arrays, calculate the sum of each pair, filter out the ones greater than 7000, sort, and take the top values that are equal. The time complexity is O(n²). Can we do better?

Answer 1

In the beginning, you should sort two arrays. Then you can use this iteration:

for every number in A:
    perform binary search to find biggest element in B lower than 7000-A

Number you found in binary search is the best number for pairing for current number in array A. You can take maximum of these values(for all iteration on array A).

Binary search runs in O(logN) time so this iteration runs in O(NlogN) time, and sort also runs in O(NlogN) time. You can change 7000 with a variable.