Find the pair across 2 arrays with kth largest sum [closed]

Question

Given two sorted arrays of numbers, we want to find the pair with the kth largest possible sum. A pair is one element from the first array and one element from the second array. For example, with arrays

• [2, 3, 5, 8, 13]
• [4, 8, 12, 16]

The pairs with largest sums are:

1. 13 + 16 = 29
2. 13 + 12 = 25
3. 8 + 16 = 24
4. 13 + 8 = 21
5. 8 + 12 = 20

So the pair with the 4th largest sum is (13, 8). How to find the pair with the kth largest possible sum?

I anticipate the solution may involve either a min heap or a max heap.

Answer 1

That can be easily done in O(k*logk). I'll only assume arrays are sorted in descending order, to simplify notation.

The idea is simple. We'll find 1st, 2nd, .., k-th maximum values one by one. But to even consider pair (i, j) we need to have both (i-1, j) and (i, j-1) already selected, because they both are greater or equal than (i, j).

It's much like if we push all n*m pairs into the heap and then remove max k times. Only we don't need all n*m pairs.

heap.add(pair(0, 0));  // biggest pair

// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
    // get max and remove it from the heap
    max = heap.popMax();

    // add next candidates
    heap.add(pair(max.i + 1, max.j));
    heap.add(pair(max.i, max.j + 1));
}

// get k-th maximum element
max = heap.popMax();
maxVal = a[max.i] + b[max.j];

Some things to consider.

• Duplicated pairs can be added to the heap, this can be prevented with hash.
• Indexes need to be validated, e.g. that max.i + 1 < a.length.