# Leetcode Find K Pairs with Smallest Sums problem solution

In this Leetcode Find K Pairs with Smallest Sums problem solution, You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array. Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

## Problem solution in Python.

```def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
maxheap=[]
for i in nums1:
for j in nums2:
s=0
s+=i+j
heappush(maxheap,[-s,[i,j]])
while(len(maxheap)>k):
heappop(maxheap)
res=[]
while maxheap:
_,i=heappop(maxheap)
res.append(i)
return res
```

## Problem solution in Java.

```public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
if(nums1==null || nums1.length==0 || nums2==null || nums2.length==0) {
return res;
}
PriorityQueue<int[]> minQ = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] pair1, int[] pair2) {
return (nums1[pair1[0]]+nums2[pair1[1]])-(nums1[pair2[0]]+nums2[pair2[1]]);
}

});

minQ.offer(new int[]{0, 0});

while (k>0 && !minQ.isEmpty()) {
int[] pair=minQ.poll();
int i = pair[0];
int j = pair[1];
k--;

if(j+1<nums2.length) {
minQ.offer(new int[]{i, j+1});
}

if(j==0 && i+1<nums1.length){
minQ.offer(new int[] {i+1, 0});
}

}

return res;
}
}
```

## Problem solution in C++.

```auto _ = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
return nullptr;
}();

class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int,vector<int>>,vector<pair<int,vector<int>>>,greater<pair<int,vector<int>>>> pq;

vector<vector<int>> ans;
for(long int i = 0; i < nums1.size(); i++)
for(long int j = 0; j < nums2.size(); j++){
vector<int> v;
v.push_back(nums1[i]);
v.push_back(nums2[j]);
pq.push(make_pair(nums1[i] + nums2[j],v));
}

while(k-- && pq.size()){
auto ele = pq.top();
ans.push_back(ele.second);
pq.pop();
}
return ans;
}
};
```

## Problem solution in C.

```int cmp(const void *a, const void *b) {
int **aa;
int **bb;

aa = (int **)a;
bb = (int **)b;

return ((*aa)[0] + (*aa)[1]) - ((*bb)[0] + (*bb)[1]);
}

int** kSmallestPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k, int* returnSize, int** returnColumnSizes){
int **arrayOfArray;
int i;
int j;
int count;

if(nums1Size==0 || nums2Size==0 || k < 1) {
*returnSize = 0;
return NULL;
}

*returnColumnSizes = (int *)malloc(sizeof(int) * nums1Size * nums2Size);
arrayOfArray = (int **)malloc(sizeof(int *) * nums1Size * nums2Size);

count = 0;
for(i = 0; i < nums1Size; i++) {
for(j = 0; j < nums2Size; j++) {
arrayOfArray[count] = (int *)malloc(sizeof(int) * 2);
(arrayOfArray[count])[0] = nums1[i];
(arrayOfArray[count])[1] = nums2[j];
(*returnColumnSizes)[count] = 2;
count++;
}
}

qsort(&arrayOfArray[0], nums1Size * nums2Size, sizeof(int *), cmp);

if(count < k) {
*returnSize = count;
} else {
*returnSize = k;
}

return arrayOfArray;
}
```