Find K Pairs with Smallest Sums
Medium · Heap & Counting · Array · Heap (Priority Queue)
Problem
You are given two integer arrays nums1 and nums2, each sorted in non-decreasing order, and an integer k. A pair [u, v] takes one element u from nums1 and one element v from nums2; elements at different positions count as different pairs even when their values are equal.
Return the k pairs with the smallest sums u + v. The pairs may be listed in any order, and when several pairs tie at the cut-off sum, any of them may be chosen.
Examples
Input: nums1 = [1,3,8], nums2 = [2,5,6], k = 4 Output: [[1,2],[3,2],[1,5],[1,6]]
The four smallest sums are 3, 5, 6 and 7.
Input: nums1 = [0,0], nums2 = [4,9], k = 3 Output: [[0,4],[0,4],[0,9]]
Each 0 pairs with 4 for a sum of 4, and the next smallest sum is 9.
Input: nums1 = [2], nums2 = [1,10], k = 2 Output: [[2,1],[2,10]]
Only two pairs exist and k asks for both.
Constraints
- 1 <= len(nums1), len(nums2) <= 10^5
- -10^9 <= nums1[i], nums2[i] <= 10^9
- Both arrays are sorted in non-decreasing order
- 1 <= k <= 10^4
- k <= len(nums1) · len(nums2)
Approaches
- Build every pair and sort — time O(m · n · log(m · n)), space O(m · n)
Follow-up
Only rows that could hold one of the k answers are started, so the heap never holds more than min(k, len(nums1)) entries. The same lane-per-row merge finds the k-th smallest element of a sorted matrix, the k-th smallest sum of three sorted arrays (two merges in a row) and the smallest fractions built from a sorted list. When only the k-th sum is wanted and values are small, a binary search on the sum, counting pairs at or below it with two pointers, avoids the heap.
Related problems
Start free on Cariara · Coding problems · System design studio
