# Untitled

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;
}
};  */```