# Evolve from brute force

• This is similar to Kth Largest Element in an Array.

1. O(mnlogmn) generate all pairs and sort them
``````   vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
if(!n1||!n2) return vector<pair<int,int>>();
vector<array<int,3>> pairs(n1*n2);
for(int i=0;i<n1;i++)
for(int j=0;j<n2;j++)
pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
sort(pairs.begin(),pairs.end());
vector<pair<int,int>> res;
for(int i=0;i<min(n1*n2,k);i++) res.push_back(make_pair(pairs[i][1],pairs[i][2]));
return res;
}
``````
1. O(mnlogk) generate all pairs, use a max heap to extract smallest k.
``````    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
if(!n1||!n2) return vector<pair<int,int>>();
vector<array<int,3>> pairs(n1*n2);
for(int i=0;i<n1;i++)
for(int j=0;j<n2;j++)
pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
priority_queue<array<int,3>,vector<array<int,3>>> heap;
for(int i=0;i<pairs.size();i++)
if(i < k ) heap.push(pairs[i]);
else if (heap.top() > pairs[i]) {
heap.pop();
heap.push(pairs[i]);
}
vector<pair<int,int>> res;
while(!heap.empty()) {
res.push_back(make_pair(heap.top()[1],heap.top()[2]));
heap.pop();
}
return res;
}
``````
1. O(mn+klogmn) generate all pairs, store them in a min heap, extract smallest k.
``````    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n1=nums1.size(),n2=nums2.size();
if(!n1||!n2) return vector<pair<int,int>>();
vector<array<int,3>> pairs(n1*n2);
for(int i=0;i<n1;i++)
for(int j=0;j<n2;j++)
pairs[i*n2+j] = array<int,3>({nums1[i]+nums2[j],nums1[i],nums2[j]});
make_heap(pairs.begin(),pairs.end(),greater<array<int,3>>());
vector<pair<int,int>> res;
for(int i=0;i<min(n1*n2,k);i++) {
res.push_back(make_pair(pairs[0][1],pairs[0][2]));
pop_heap(pairs.begin(),pairs.end(),greater<array<int,3>>());
pairs.pop_back();
}
return res;
}
``````
1. O(klogk)
``````    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int,int>> res;
if(nums1.empty() || nums2.empty()) return res;
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq;
pq.push(array<int,3>({nums1[0]+nums2[0],0,0}));
while(!pq.empty() && res.size()<k) {
int i=pq.top()[1], j = pq.top()[2];
pq.pop();
res.push_back(pair<int,int>(nums1[i],nums2[j]));
if(!j && i+1<nums1.size()) pq.push(array<int,3>({nums1[i+1]+nums2[0],i+1,0}));
if(j+1<nums2.size()) pq.push(array<int,3>({nums1[i]+nums2[j+1],i,j+1}));
}
return res;
}
``````

• Where's the optimal one?

• @StefanPochmann I thought #4 O(klogk) is optimal? Correct me if it is not.

• @StefanPochmann Thanks for the info. The solution does not look easy to understand...I remove "optimal" from the title...

• @yu6 Yeah, it's definitely not easy. At least not the part I only referenced there, from the other problem/solution. That's why I was curious how you did it :-)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.