Find the pair across 2 arrays with kth largest sum

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.

Answer 2

I understand you want a heap but that isn't the most efficient solution, as phimuemue pointed out.

You can max_heap both arrays, and set an iterator at the root for both. At this point, you have the largest sum.

Now, at each step, find the maximum, unvisited node among the children and neighbors of both pointers -- this is the next largest sum. Move the pointer in the corresponding heap there.

Repeat k times.

Answer 3

Here is my answer, I think it's working well, but could someone tell me what's its complexity ?

Thanks

int ksum( int a[], int n, int b[], int m, int maxk )
{

    std::vector<int> results;
    int* check = new int[m*n];
    memset( check, 0, n*m*sizeof(int) );

    int finali, finalj;
    int starti = 0, startj = 0;
    for( int k=1; k<maxk+1; ++k )
    {
        int max = 0;
        int maxi=n, maxj=m;
        for( int i=starti; i<n && i<k; ++i )
        {
            if( i>maxj )
                break;
            for( int j=i; j<m && j<k; ++j )
            {
                if( i>maxi && j>=maxj )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        starti = finali;

        maxi=n, maxj=m;
        for( int j=startj; j<n && j<k; ++j )
        {
            if( j>maxi )
                break;
            for( int i=j; i<m && i<k; ++i )
            {
                if( j>maxj && i>=maxi )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        startj = finalj;

        if( max > 0 )
        {
            check[finali*m+finalj] = 1;
            results.push_back( max );
        }
    }

    delete[] check;
    if( maxk > results.size() )
        return 0;
    else
        return results[maxk-1];
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[] = {10,8,6,4,1};
    int b[] = {9,6,3,2,1};
    int res = ksum( a, 5, b, 5, 9 );
    return 0;
}