Find K Pairs with Smallest Sums
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
