Skip to main content

Find K Pairs with Smallest Sums

Question​

Given two integer arrays of size m and n, find the k pairs (one from each array) with the smallest sums.

Example 1
Input: nums1 = [1,2,4,5,7], nums2 = [3,5,6,8]
K = 3

Output: [ [1,3], [2,3], [4,5] ]

Solution​

all//Find K Pairs with Smallest Sums.py


def findKPairsSmallestSums(nums1, nums2, k):
    minHeap = []
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            sumOfPair = nums1[i] + nums2[j]
            if len(minHeap) < k:
                heapq.heappush(minHeap, (sumOfPair, [nums1[i], nums2[j]]))
            else:
                if sumOfPair < minHeap[0][0]:
                    heapq.heappushpop(minHeap, (sumOfPair, [nums1[i], nums2[j]]))
    return minHeap