# Two c++ solutions (36ms and 16ms)

• O(n*k) solution 36ms

``````vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int,int>> res;
vector<int> pos(nums1.size());
int sz1 = nums1.size(), sz2 = nums2.size();
int cnt  = 0;
if(sz1 == 0 || sz2== 0)
return res;

while(cnt < k){
int minSum = INT_MAX;
int nxt = -1;
for(int j = 0; j < sz1; j++){
if(pos[j] < sz2 && nums1[j]+ nums2[pos[j]] < minSum){
nxt = j;
minSum =nums1[j]+ nums2[pos[j]];
}
}
if(nxt == -1){
break;
}
res.push_back(make_pair(nums1[nxt], nums2[pos[nxt]]));
pos[nxt]++;
cnt++;
}

return res;
}
``````

O(K*log(n)) solution. Use priority queue to reduce the time for finding the min sum, 16 ms

``````    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<pair<int,int>> res;
vector<int> pos(nums1.size());
int sz1 = nums1.size(), sz2 = nums2.size();
int cnt  = 0;
if(sz1 == 0 || sz2== 0)
return res;
auto cmp = [](pair<int,int> a, pair<int,int> b){
return (a.first > b.first);
};
priority_queue<pair<int,int> ,vector<pair<int,int>> , decltype(cmp)> q(cmp);

for(int j = 0; j < sz1; j++){
q.push(make_pair(nums1[j]+ nums2[0], j));
}

while(cnt < k && q.size() > 0){
res.push_back(make_pair(nums1[q.top().second], nums2[pos[q.top().second]]));
int j = q.top().second;
q.pop();
pos[j]++;
cnt++;
if(pos[j] < sz2)
q.push(make_pair(nums1[j]+nums2[pos[j]], j));
}
return res;
}
``````

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