Find K Pairs with Smallest Sums

Medium#373merge k lists

You get two arrays sorted in ascending order and a number k. A pair takes one number from each array. Return the k pairs with the smallest sums. Our example: [1, 4, 6], [2, 3, 9] and k = 4 — the answer is [1, 2], [1, 3], [4, 2] and [4, 3], with sums 3, 4, 6 and 7.

373 Find K Pairs with Smallest SumsWalkthrough · 1×

Example: nums1 = [1, 4, 6], nums2 = [2, 3, 9], k = 4. Row i holds the sums nums1[i] + nums2[j]; each row grows to the right, like a sorted list.

nums2239nums1[0] = 13410nums1[1] = 46713nums1[2] = 68915heapsmallest on the left368result—
not in the heap yetin the heapjust popped or addedin the result

Each row starts with its first pair, nums2[0] = 2: the sums 3, 6 and 8 go into the heap

01/24
restart · back · play · step
Speed
1function kSmallestPairs(nums1, nums2, k):
2 heap = min-heap of (nums1[i] + nums2[0], i, 0) for each i
3 result = []
4 while size of result < k and heap is not empty:
5 (s, i, j) = pop min from heap
6 add [nums1[i], nums2[j]] to result
7 if j + 1 < len(nums2):
8 push (nums1[i] + nums2[j + 1], i, j + 1) into heap
9 return result
state
heap
[3, 6, 8]
result
–
s
–
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. nums2 is sorted, so each row of sums grows to the right. The pairs are k sorted lists, one per row, and the next smallest sum is always the first unused pair of some row.
  2. The heap holds exactly that first unused pair of every row, so its top is the next smallest sum. After a pop, the row moves on by one pair.
  3. The run stops after k pops: pairs further right in each row are never built, like the 9s here.

Complexity

Time O(n + k log n), where n is the length of nums1: a heap of one pair per row, then k pops and at most k pushes. Memory O(n + k) for the heap and the answer.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.