Find K Pairs with Smallest Sums

Medium· min-heap· k-way merge

Problem

You are given two ascending integer arrays and a number k. A pair takes one element from each array. Return the k pairs whose sums are smallest.

Examples

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Output: [[1,2],[1,4],[1,6]]

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Output: [[1,1],[1,1]]

Constraints

• 1 <= nums1.length, nums2.length <= 10^5
• Both arrays are sorted ascending
• 1 <= k <= 10^4

Hints & approach

Hint 1

Generating all n * m pairs is far too many.

Hint 2

Think of it as merging n sorted lists, where list i is nums1[i] paired with each nums2[j].

Hint 3

Seed a min-heap with (i, 0) for the first k values of i, then advance j after each pop.

Approachtry the hints first

Treat each nums1[i] as the head of a sorted list of pairs (nums1[i], nums2[j]) for increasing j. Push (nums1[i] + nums2[0], i, 0) for the first min(k, n) indices into a min-heap. Pop the smallest sum k times; after popping (i, j), record the pair and, if j + 1 is in range, push (i, j + 1). This is k-way merge on implicit lists, so only O(k) entries ever enter the heap.

Time O(k log k) · Space O(k)

← PreviousK Closest Points to Origin Next →Reorganize String