N Max Pair Combinations

Problem Description

In this problem, we have two integer arrays/integer vectors, and our task here is to return an integer vector of a size similar to the arrays and containing the max pair sum elements of the two arrays.

We’ll take one element from vector 1 and another element from vector 2 in such a way that the sum of both elements is maximum and then put the sum in the result vector. Next time, we’ll select another pair of elements such that their sum is the second maximum, and we’ll push it in the result vector; this will go on until there are n elements (size of vector 1 and vector 2) in the result vector.

(Also see, Data Structures)

Example

A = [1, 4, 2, 3]

B = [2, 5, 1, 6]

The max sum vector will be [10, 9, 9, 8] for the following two vectors.

Here, 10 is the maximum pair sum we can get by adding 4 and 6 from vectors A and B, respectively.

After that, the second max pair sum that we can get here is either by adding 4 with 5 or by adding 3 with 6, so we’ll add 9 two times in the resultant vector.

Finally, the fourth element of the vector will be 8, which we’ll get after adding 3 and 5 from A and B, respectively.

vec[0] = 4 (A) + 6 (B) = 10,

vec[1] = 3 (A) + 6 (B) = 9,

vec[2] = 5 (A) + 4 (B) = 9, and

vec[3] = 3 (A) + 5 (B) = 8.

Also Read, Prefix Sum Array

Algorithm

Heap or the Priority queue is the first thing that comes to mind when asked to find some maximum or minimum element efficiently in O(1) time. Hence, since we have to find N maximum pair sum, we’ll formulate an approach using a max heap.

The first step we’ll be to sort the given two vectors because since we are trying to find the maximum sum, sorting is an excellent idea to start.

Next, we’ll initialize a max priority queue (max heap). We’ll use this priority queue to store a tuple containing three elements (sum of the pair, element index in vector A, element index in vector B).

Now, we’ll populate the priority queue with the elements of vector A added with the maximum element in vector B. For instance, if we vector A = {1, 4, 2, 3} and vector B = {2, 5, 1, 6} then the max heap will look like this-

In the next step, we’ll declare a result vector and push the top of the priority queue (maximum sum) in the vector; after pushing, we’ll also remove this from the priority queue. We’ll iterate the above step n times.

Each of the new tuples contains the sum of the maximum element in vector A and the next maximum element of vector B (decreasing index means we take one element smaller than the maximum element each time).

Finally, we return the result vector!

(Also see, Heap and Priority Queue)

Implementation

#include<bits/stdc++.h>
using namespace std;

// Function to return the max-sum pair vector
vector<int> maxSumVector(vector<int> &A, vector<int> &B){
    
    // Sorting both the given vectors
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    int n = A.size();
    
    // This priority_queue stores a tuple
    // tuple = (sum of pair, index of A used for the sum, index of B used for the sum)
    priority_queue<tuple<int, int, int>> pq;
    
    // The last indexes of both the vectors will give the max pair sum
    // Taking the maximum element from vector B and pushing all pair sums with vector A in the priority queue
    for(int i=0; i<n; i++){
        pq.push({A[n-1-i] + B[n-1], n-i-1, n-1});
    }
    
    vector<int> result;
    while(n-->0){
        
        // At any instance, the top of the priority queue will be pushed to the vector
        // ia is the index of the element in vector A, and ib is the index of the element in vector B
        auto[sum, ia, ib] = pq.top();
        pq.pop();
        result.push_back(sum);
        
        pq.push({A[ia] + B[ib-1], ia, ib-1});
    }
    
    return result;
}
int main()
{
    //vector<int> A = {1, 4, 2, 3};
    //vector<int> B = {2, 5, 1, 6};
    int n;
    cin>>n;
    
    vector<int> A;
    vector<int> B;
    
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        A.push_back(a);
    }
    
    for(int i=0; i<n; i++){
        int b;
        cin>>b;
        B.push_back(b);
    }
    
    vector<int> result = maxSumVector(A, B);
    
    for(int i=0; i<result.size(); i++) cout<<result[i]<<" ";
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Sample Input 1

4
1 4 2 3
2 5 1 6

Sample Output 1

10 9 9 8

Sample Input 2

6
1 4 2 3 8 9
2 5 1 6 11 45

Sample Output 2

54 53 49 48 47 46