Home » Interview coding problems/challenges

N Max Pair Combinations

Here, we are going to find the solution of N Max Pair Combinations using various approaches.
Submitted by Divyansh Jaipuriyar, on April 13, 2021

Problem Statement:

Given two arrays A and B of size N each, find the maximum N elements from the sum combination (A[i]+B[j]) formed elements A and B. You can only combine elements of two arrays you can't combine the same array elements.

Problem Description:

The problem wants you to use two arrays as given and find the maximum sum that you can get from both the arrays such that the pair elements belong to 1st and 2nd array, keeping in mind that you cannot use the same array elements it will be against the problem statement i.e., if you are using a[i] and b[j] then they belong to two arrays respectively.

Input: The first line of the input consists of T number of test cases. Each test case consists of N size of the array. Followed by two lines are array A and B respectively.

Output: Print the maximum N elements after combining from both the arrays in a separate line for each test case.

Example:

Input:
T = 1
N = 4
[1,4,2,3]
[2,5,1,6]

Output:
10, (4+6)
9, (3+6)
9, (4+5)
8, (2+6)

All the above elements are the n pairs 
with maximum sum that we can obtain.

Solution Approach:

(1) Brute Force Approach:

In this approach, we will use a two-loop and iterate through all combinations of the elements and store them in a heap or a vector. If we are storing them in a max heap then we pop the top element from the heap n times since the top of the heap is the maximum sum elements and if we are storing sum combination in vector then we need to sort the vector and then we take n max sum combination from it.

The above logic can be implemented with the help of vector and priority_queue that is a heap data structure.

• Time Complexity for the above approach is O(n*n)
• Space Complexity for the above approach is O(n*n)

Program:

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of arrays: ";
        ll n;
        cin >> n;

        ll A[n], B[n];
        cout << "Enter elements:\n";
        for (ll i = 0; i < n; i++)
            cin >> A[i];

        for (ll i = 0; i < n; i++)
            cin >> B[i];

        //declare heap.
        priority_queue<ll> p;

        //iterate through outer loop A.
        for (ll i = 0; i < n; i++) {
            //iterate through inner loop B.
            for (ll j = 0; j < n; j++) {
                p.push(A[i] + B[j]);
            }
        }

        //declare vector to store make n max sum combination.
        vector<ll> v1;

        //iterate through n elements from heap.
        while (n--) {
            //store max elements and pop it from the heap.
            v1.push_back(p.top());
            p.pop();
        }

        //final max sum combination.
        for (ll i = 0; i < v1.size(); i++)
            cout << v1[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of arrays: 4
Enter elements:
4 5 6 7
2 3 8 9
16 15 15 14 
Enter size of arrays: 3
Enter elements:
11 22 33
1 2 3
36 35 34 
Enter size of arrays: 5
Enter elements:
1 2 3 4 5
10 11 12 13 14   
19 18 18 17 17 

(2) Better Approach:

In this approach, we will use the priority queue with pairs and set for managing the indices that we have used that are remaining. We need to sort both the arrays and store their last elements in the max heap which we create with help of priority_queue and pairs.

priority_queue<pair<int, pair<int, int>>> heap, the first pair consists of sum and another pair for indices from which the sum has been obtained. To avoid the duplicacy of array elements we will use either a map or set with pairs. We need to repeat the process n times to get the maximum sum pairs, in each step we will check the indices pair {l,r-1} and {l-1,r} for storing it in the heap after processing the previous indices {l,r}.

• Time Complexity for the above case: O(Nlog(N)
• Space Complexity for above cases: O(N)

Program:

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of arrays: ";
        ll n;
        cin >> n;

        cout << "Enter elements :\n";
        ll A[n], B[n];
        for (ll i = 0; i < n; i++)
            cin >> A[i];
        for (ll i = 0; i < n; i++)
            cin >> B[i];

        //priority_queue(heap)with pair as its elements.
        priority_queue<pair<ll, pair<ll, ll> > > pq;

        //declare set with pairs to store indices pairs.
        set<pair<ll, ll> > st;

        //sort both the arrays.
        sort(A, A + n);
        sort(B, B + n);

        //push the first maximum element in the heap.
        pq.push({ (A[n - 1] + B[n - 1]), { n - 1, n - 1 } });

        //insert the indices pair in set.
        st.insert({ n - 1, n - 1 });

        //pair variable for further operations.
        pair<ll, pair<ll, ll> > p;
        //declare vector to store sum combination in it.
        vector<ll> v1;

        while (n--) {
            //take the maximum sum combination from heap.
            p = pq.top();
            pq.pop();
            ll l = p.second.first; //store A[] array index in l.
            ll r = p.second.second; //store B[] array index in r.
            v1.push_back(p.first); //store sum in vector.

            //check for other cases as second last indices and
            //list indices from the {l,r}
            if (l > 0 and r >= 0 and st.find({ l - 1, r }) == st.end()) {
                st.insert({ l - 1, r });
                pq.push({ (A[l - 1] + B[r]), { l - 1, r } });
            }
            if (l >= 0 and r > 0 and st.find({ l, r - 1 }) == st.end()) {
                st.insert({ l, r - 1 });
                pq.push({ (A[l] + B[r - 1]), { l, r - 1 } });
            }
        }

        cout << "Final result: ";
        for (ll i = 0; i < v1.size(); i++)
            cout << v1[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 2
Enter size of arrays: 4
Enter elements :
1 2 3 4
10 9 8 7
Final result: 14 13 13 12 
Enter size of arrays: 5
Enter elements :
1 2 3 4 5
11 22 33 44 55
Final result: 60 59 58 57 56