Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
2.4 kB
0
Indexable
Never
 class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int n=nums1.size(), m=nums2.size();
        vector<vector<int>> ans;
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>> ,greater<pair<int,pair<int,int>>>> pq;
        for(int i=0;i<n;i++){
            pq.push({nums1[i]+nums2[0],{i,0}});
        }
        while(!pq.empty() && k--){

            pair<int,pair<int,int>> tmp=pq.top();
            pq.pop();
            int x=tmp.second.first;
             int y=tmp.second.second;

            ans.push_back({nums1[x],nums2[y]});

            if(y!=m-1){
                pq.push({nums1[x]+nums2[y+1],{x,y+1}}); 
            }
        }
        return ans;
    }
};



/* 
class small{
    public:
    bool operator()(const int& a,const int& b){
        return a>b;
    }
};


class Solution {  //wrong approach
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<int,vector<int>,small> pq1;
        priority_queue<int,vector<int>,small> pq2;
        for(int i=0;i<nums1.size();i++) pq1.push(nums1[i]);
        for(int i=0;i<nums2.size();i++) pq2.push(nums2[i]);
        vector<vector<int>> ans;

        while(k>0 && pq1.size()>1 && pq2.size()>1){ // NO CHEKS FOR EMPTYNESS  
            if(pq1.top() < pq2.top()){
                int t2=pq2.top();
                pq2.pop();
                ans.push_back({pq1.top(),t2});
            }
            else{
                int t1=pq1.top();
                pq1.pop();
                ans.push_back({t1,pq2.top()});
            }
            k--;
            //if(pq1.empty() || pq2.empty()) break;
        }
        if(k==0) return ans;

        if(pq1.size()==1 && pq2.size()>1){
            int t1=pq1.top();
            while(k>0 && !pq2.empty()){
                int t2=pq2.top();
                pq2.pop();
                ans.push_back({t1,t2});
                k--;
            }
        }

        if(pq1.size()>1 && pq2.size()==1){
            int t2=pq2.top();
            while(k>0 && !pq1.empty()){
                int t1=pq1.top();
                pq1.pop();
                ans.push_back({t1,t2});
                k--;
            }
        }
        return ans;
    }
};  */