 # N max sum pairs

Given two arrays A & B of size N each.
Find the maximum n elements from the sum combinations (Ai + Bj) formed from elements in array A and B.

For example if A = [1,2], B = [3,4], then possible pair sums can be 1+3 = 4 , 1+4=5 , 2+3=5 , 2+4=6
and maximum 2 elements are 6, 5

Example:

N = 4
a[]={1,4,2,3}
b[]={2,5,1,6}

Maximum 4 elements of combinations sum are
10 (4+6),
9 (3+9),
9 (4+5),
8 (2+6)

1 Like

Sort both array A and B.

Now insert maximum pair i.e. (An , Bn, |An - Bn|) pair in heap(max Heap)

on each iteration extract max pair from heap let call it (Ai, Bj, |Ai - Bj|)

insert pair (Ai, Bj-1, |…|) and (Ai-1, Bj, |…|) in heap.

This way you can iterate on max pair

Time complexity O(nlogN)

2 Likes

Along with what @aya_cool
said, Instead of Heap you could use Priority Queue and also keep in mind the number of insertions since it is a costly operation, this can be done by keeping a map in check of the numbers which are already present in the PriorityQueue. Or you could use Some Data Structures like TreeMap in Java, in case you do in Java. TreeMap is a combination of HashMap and sorted Keys based on Custom Comparator (might be ascending or descending here in case descending). Hope it helps…

2 Likes

How would we implement this in Java since we don’t have “pair” in Java ?

which pair is aya_cool taking about. He’s saying pair but writing 3 terms. Which two form the pair? And how to get the sum?

First, sort the arrays A and B. Then initialize a max heap with the tuple (A[n-1]+B[n-1],\ n,\ n). You can use a `priority_queue` in C++ and a `TreeMap` in Java as @ssaxena36 has said. The heap should be ordered by the first value, the order of the rest does not matter. Then pop the heap to get the current largest sum and the indices of the elements in A and B which make up this sum. Let this popped tuple be (sum,\ i,\ j). Next insert (A[i]+B[j-1],\ i,\ j-1) and (A[i-1]+B[j],\ i-1,\ j) into the heap. Repeat this procedure n times to get the n largest sums.

Actually priority queue is an abstract data structure, which is usually implemented as a heap. So using a priority queue instead of a heap does not make sense.

1 Like

Yes, i understand that I meant as in inbuilt Data Structure i.e. STL Container Adapter std::priority_queue. Even Tree Map uses RB Tree, for implementation, that’s what i was trying to point out. But where efficiency matters, you wont prefer writing whole MaxHeapify functions.

1 Like

Ah I get you now. Yes, of course, using stl is preferable to implementing one’s own heap you can make a class named Pair
class Pair{
int x,y;
}

1 Like

By pair I suppose @aya_cool meant `pair<int, pair<int, int>>`, and I realize now that his solution is actually not correct.

1 Like