# My 9ms C++ 20+lines solution, O(n+k*logn)-time O(n)-space beats 99.64%.

• ``````//indexed-array+heap-9ms; O(n+k*logn)
#define npos first
#define sum second
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
if(nums1.empty()||nums2.empty()) return vector<pair<int,int>>(0);
int n=nums1.size(),m=nums2.size();
int pos[n]{0};
pair<int,int> heap[n];
vector<pair<int,int>> ans(0);
for(int i=0;i<n;++i) heap[i].npos=i,heap[i].sum=nums1[i]+nums2[0];
k=min(k,n*m);
while(k--){
ans.push_back(pair<int,int>(nums1[heap[0].npos],nums2[pos[heap[0].npos]]));
heap[0].sum=(++pos[heap[0].npos]==m)?INT_MAX:(nums1[heap[0].npos]+nums2[pos[heap[0].npos]]);
for(int p=-1,minp=0;minp!=p;){
p=minp;
int next=p<<1;
if(++next<n&&heap[next].sum<heap[minp].sum) minp=next;
if(++next<n&&heap[next].sum<heap[minp].sum) minp=next;
swap(heap[p],heap[minp]);
}
}
return ans;
}
};``````

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