Simple C++ O(Clog(C)) solution


#1

// Code by Prateek Mishra IIT2018199, IIIT Allahabad.

//UNDERSTANDING THE APPROACH
/* We here use the concept of merging k - sorted linked lists.
Let the given vectors after sorting be
A : 16, 11, 7, 1
B : 15, 10, 9, 2

Now we know that 4 ^ 4 different sums are possible for this combination and we need to
find the largest C out of these. Let the pairs be:
(16,15), (16,10), (16,9), (16,2),
(11,15), (11,10), (11,9), (11,2),
(7,15), (7,10), (7,9), (7,2),
(1,15), (1,10), (1,9), (1,2),

Note that the numbers (pair of the sums) in every row are sorted in descending order. Now we
need to merge these sorted LinkedLists.
*/

vector<int> Solution::solve(vector<int> &A, vector<int> &B, int C)
{
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend()); //sorting both the lists in descending order.
    priority_queue<pair<int, pair<int, int>>> maxh; //max heap for storing (sum, (i - index, j - index))

    for (int i = 0; i < C; i++) //pushing the heads of all the linked lists.
    {
        maxh.push(make_pair(B[0] + A[i], make_pair(0, i)));
    }

    std::vector<int> ans;
    while(ans.size() < C)
    {
        auto maxele = maxh.top(); maxh.pop(); 
        ans.emplace_back(maxele.first); //pushing the top to ans and inserting head -> next.
        maxh.push(make_pair(B[maxele.second.first + 1] + A[maxele.second.second], make_pair(maxele.second.first + 1, maxele.second.second)));
    }
    return ans;
}

#2

great approach and well written.:+1::+1:, thanks!


#3

Same Merge sorted list approach as above, concise C++ code

vector<int> Solution::solve(vector<int> &A, vector<int> &B, int C) {
    vector<int>res;
    priority_queue<tuple<int, int, int>>q;
    sort(A.rbegin(), A.rend()); 
    sort(B.rbegin(), B.rend());
    for(int i=0; i<C; i++) {
        q.push({A[i]+B[0], i, 0});
    }
    while(res.size()<C) {
        auto [sum, i, j] = q.top(); q.pop();
        res.push_back(sum);
        q.push({A[i]+B[j+1], i, j+1});
    }
    return res;
}

#4

This one is short and crisp.
Nice, Shot Champ…