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.

&nbsp;
Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]


Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]


Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]


&nbsp;
Constraints:


	1 &lt;= nums1.length, nums2.length &lt;= 105
	-109 &lt;= nums1[i], nums2[i] &lt;= 109
	nums1 and nums2 both are sorted in ascending order.
	1 &lt;= k &lt;= 104


import heapq
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:

        ans = []

        heapq.heapify(ans)

        for i in range(min(k,len(nums1))):
            for j in range(min(k,len(nums2))):
                pairs = [nums1[i],nums2[j]]
                if len(ans)<k:
                    heapq.heappush(ans,[-(nums1[i]+nums2[j]),pairs])
                else:
                    if nums1[i]+nums2[j]>-ans[0][0]:
                        break
                    heapq.heappush(ans,[-(nums1[i]+nums2[j]),pairs])
                    heapq.heappop(ans)

        res = []
        for i in range(len(ans)):
            res.append(ans[i][1])

        return res
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int []> pq = new PriorityQueue<>(
            (a, b) -> (a[0] + a[1]) - (b[0] + b[1])
        );
        for(int i = 0; i < nums1.length && i < k; i++){
            pq.add(new int[]{nums1[i], nums2[0], 0});
        }

        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < k && !pq.isEmpty(); i++){
            int [] curr = pq.poll();
            res.add(Arrays.asList(curr[0], curr[1]));
            int idx2 = curr[2];
            if(idx2 < nums2.length - 1){
                pq.add(new int[]{curr[0], nums2[idx2 + 1], idx2 + 1});
            }
        }
        return res;
    }
}
class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<pair<int,pair<int,int>>> pq;
        int m=nums1.size(),n=nums2.size();

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int sum=nums1[i]+nums2[j];
                if(pq.size()<k){
                    pq.push({sum,{nums1[i],nums2[j]}});
                }else if(sum<pq.top().first){
                    pq.pop();
                    pq.push({sum,{nums1[i],nums2[j]}});
                }else break;
            }
        }

        vector<vector<int>> ans;
        while(!pq.empty()){
            auto p=pq.top().second;
            pq.pop();

            ans.push_back({p.first,p.second});
        }

        return ans;
    }
};
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number[][]}
 */

var kSmallestPairs = function(nums1, nums2, k) {
    const h = new MinHeap();
    h.sortKey = 'id';
    for(i =0; i<nums1.length; i++)
        h.push({id: nums1[i]+nums2[0], i: i, j: 0});
    let res = [];
    while(k--){
        const t = h.pop();
        if(!t) return res;
        let {i, j} =t;
        res.push([nums1[i], nums2[j]]);
        if(j< nums2.length-1)
            h.push({id: nums1[i]+nums2[j+1], i, j: j+1});
    }
    return res;
};


/*
This is a heap class that I wrote it myself,
neat? IDK
bad? IDK
bug? IDK (tested a few times for both min and max heaps)
so use it at your own risk :)
*/
class Heap{
	constructor(arr = [], sortKey=null){
		this.heap = [];
		this.sortKey = sortKey;
		if(arr && arr.length)
			this.buildHeap(arr);
	}
    
	push(val){
		this.heap.push(val);
		this.heapUp(this.heap.length-1);
	}

	pop(){
		if(!this.heap.length) return null;
		if(this.heap.length==1) return this.heap.pop();
		const res = this.heap[0];
		this.heap[0] = this.heap.pop();
		this.heapDown(0);
		return res;
	}


	id(i){
		if(this.sortKey!==null) return this.heap[i][this.sortKey];
		return this.heap[i];
	}

	swap(i, j){
		const t = this.heap[i];
		this.heap[i] = this.heap[j];
		this.heap[j] = t;
	}
	/*for child class to implement*/
	heapUp(i){
		//heap up
	}

	heapDown(i){
		//heap down
	}

	buildHeap(list){
		//build heap
		for(let i of list)
			this.push(i);
	}

	toString(){
		return this.heap;
	}

}


class MinHeap extends Heap{
	heapUp(i){
		const pI = (i-1)>>1;
		if(pI<0) return;
		if(this.id(i)<this.id(pI)){
		 	this.swap(i, pI);
		 	return this.heapUp(pI);
		}
	}

	heapDown(i){
		const lI = i*2+1;
		const rI = i*2+2;
		if(lI>=this.heap.length) return;
		const v = Math.min(this.id(i), this.id(lI), (rI>=this.heap.length)?Number.MAX_VALUE:this.id(rI));
		if(v==this.id(i)) return;
		if(v==this.id(lI)){
			this.swap(i, lI);
			return this.heapDown(lI);
		}
		this.swap(i, rI);
		this.heapDown(rI);
	}
}


class MaxHeap extends Heap{
	heapUp(i){
		const pI = (i-1)>>1;
		if(pI<0) return;
		if(this.id(i)>this.id(pI)){
		 	this.swap(i, pI);
		 	return this.heapUp(pI);
		}
	}

	heapDown(i){
		const lI = i*2+1;
		const rI = i*2+2;
		if(lI>=this.heap.length) return;
		const v = Math.max(this.id(i), this.id(lI), (rI>=this.heap.length)?Number.MIN_VALUE:this.id(rI));
		if(v==this.id(i)) return;
		if(v==this.id(lI)){
			this.swap(i, lI);
			return this.heapDown(lI);
		}
		this.swap(i, rI);
		this.heapDown(rI);
	}
}
Find K Pairs with Smallest Sums