# O(k log(n) ) solution ,using priority queues.

• Some observations,

Since the arrays are sorted.
nums1[i] + nums2[j1] < nums1[i] + nums2[j2] , for j1< j2
This problem is similar to merging n linked list into one , or the same way n arrays should be merged,

``````class mycomp{
public:
bool operator()(pair<int,int> x ,pair<int,int> y)
{
return x.second > y.second;
}
};
class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int i,j,l1,l2;
l1 = nums1.size();
l2 = nums2.size();
vector<pair<int,int> > ans;
k = min(k,l1*l2);
if(k==0)
return ans;
int dp[l1];
for(i=0;i<l1;i++)
dp[i] = 0;
priority_queue < pair<int,int> ,vector<pair<int,int> > , mycomp > small;
pair<int,int> temp;
for(i=0;i<l1;i++)
{
small.push(make_pair(i,nums1[i]+nums2[0]));
}
while(ans.size() != k)
{
temp = small.top();
small.pop();
ans.push_back(make_pair(nums1[temp.first],nums2[dp[temp.first]]));
dp[temp.first]++;
if(dp[temp.first]< l2)
{
small.push(make_pair(temp.first,nums1[temp.first]+nums2[dp[temp.first]]));
}
}
return ans;
}
};
``````

Time Complexity : O ( k log(n) )
Space Complexity : O(k)

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