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) {
        List<int[]> res = new LinkedList<>();
        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];
            res.add(new int[]{nums1[i], nums2[j]});
            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;
}