Skip to main content

Find K Pairs with Smallest Sums


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] ]


all//Find K Pairs with Smallest

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]]))
if sumOfPair < minHeap[0][0]:
heapq.heappushpop(minHeap, (sumOfPair, [nums1[i], nums2[j]]))
return minHeap