Simple C++ O(nlog(n)) 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…


#5

It was a better approach, Prateek Sir. I was using a map to find whether a particular pair of index was already there in the heap or not. But relating it with the merging of K-Sorted Linked lists problem made my day. Thanks! Just one thing to note is that the time complexity of this solution would be O(nlogn) not O(clogc). Here’s my solution :

#define mp make_pair
#define pb push_back
vector<int> Solution::solve(vector<int> &A, vector<int> &B, int C)
{
  priority_queue<pair<int,pair<int,int> > >  heap; // max heap to store the sum along with the indexes from which the sum came from
  sort(A.rbegin(),A.rend()); // sorting array A in descending order
  sort(B.rbegin(),B.rend()); // sorting array B in descending order
  map<pair<int,int>,bool > m; // map to be used as a vis array whether index (i,j)'s sum is already present int the heap or not
  heap.push(mp(A[0]+A[0],mp(0,0))); // Initially pushing the sum of the biggest elements from both the arrays (Ofcourse it would be the biggest sum combination for our solution)
  m[mp(0,0)]=true; // this represent that sum from (0,0) is already present in the heap
  vector<int> ans;
  while(ans.size()<C) // now find the top elements and keep pushing the (i+1,j) & (i,j+1)th sum cobinations in the heap (remeber that the top of the heap would only contain the maximum sum)
  {
      pair<int,pair<int,int> > temp = heap.top();
      heap.pop();
      int sum = temp.first;
      ans.pb(sum);
      int ind1 = temp.second.first;
      int ind2 = temp.second.second;
      if(m[mp(ind1+1,ind2)]!=true){
          heap.push(mp(A[ind1+1]+A[ind2],mp(ind1+1,ind2)));
          m[mp(ind1+1,ind2)] = true;
      }
      if(m[mp(ind1,ind2+1)]!=true){
          heap.push(mp(A[ind1]+A[ind2+1],mp(ind1,ind2+1)));
          m[mp(ind1,ind2+1)] = true;
      }
      
  }
  return ans;
}

#6

UPD1 : The time complexity of the code will be O(nlog(n)) as pointed out by @pranav-singhal (Thanks dude!). I am not able to find any way to update the post, please let me know if there is any.