373 - heap

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        if not (nums1 and nums2):
            return []
        h = [(nums1[i] + nums2[0], i, 0) for i in range(len(nums1))]
        heapq.heapify(h)
        res = []
        while k and h:
            val, i, j = heapq.heappop(h)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(h, (nums1[i] + nums2[j+1], i, j+1))
            k -= 1
        return res