Find K Pairs with Smallest Sums
Return up to k index pairs with the smallest sums from two sorted arrays.
- 1 <= nums1.length, nums2.length <= 10⁵
- -10⁹ <= nums1[i], nums2[i] <= 10⁹
- nums1 and nums2 both are sorted in non-decreasing order.
- 1 <= k <= 10⁴
- k <= nums1.length * nums2.length
Intuition
Find k pairs with smallest sums takes two sorted arrays and asks for the k pairs with the smallest sums. Generating all n·m pairs and sorting costs O(nm log nm), which is wasteful when k is small — you would be ordering millions of pairs to keep ten.
Think of the pairs as a grid where row i holds the sums nums1[i] + nums2[j] for increasing j. Because nums2 is sorted, each row is itself sorted left to right. And because nums1 is sorted, the rows start in increasing order.
So the task is merging several sorted rows and taking the first k values — exactly the k-way merge that a min-heap handles. The heap holds one candidate per active row, and popping the smallest advances only the row it came from:
- Pop the smallest pair, output it, then push the next pair from that same row.
Two details keep it efficient. Seed the heap with only the first min(k, n) rows, since a later row's first element cannot beat k earlier row heads when nums1 is sorted — seeding all n rows wastes space for no benefit.
And advance only within the popped row. Pushing both a rightward and a downward neighbour, as in some grid problems, would let the same cell arrive twice and require a visited set. Seeding one entry per row and stepping only rightward makes duplicates impossible by construction.
Combining elements from sorted inputs often forms a monotone grid or sorted rows. If only the first k combinations are required, use best-first heap expansion instead of materializing the entire Cartesian product.
Approach
Before reading on: price up what sorting first costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(k log min(k, m)) time and O(min(k, m)) space.
See the pairs as sorted rows
Row i holds nums1[i] + nums2[j] for increasing j, and is sorted because nums2 is. The problem becomes a k-way merge of these rows, which is a well-known heap pattern rather than a novel search.
Seed only the first min(k, n) rows
Push (nums1[i] + nums2[0], i, 0) for the first min(k, len(nums1)) rows. Later rows start with a larger sum than these, so they cannot contribute to the first k results — seeding all rows wastes memory without changing the answer.
Pop the globally smallest head
The heap's minimum is the smallest sum not yet emitted, since every row's unexplored remainder is larger than its own current head. Append that pair to the output and count it toward k.
Advance within the popped row only
Push (nums1[i] + nums2[j+1], i, j+1) if that column exists. Stepping only rightward makes duplicates structurally impossible — no visited set is needed, unlike grid problems that also move downward.
Stop at k or when the heap empties
Terminate once k pairs have been emitted, or earlier if the heap runs dry because every possible pair was consumed. The problem allows returning fewer than k when n·m < k.
Cost of the merge
The heap holds at most min(k, n) entries, and each of the k pops does O(log k) work, giving O(k log k) time after seeding. Compare with O(nm log nm) for generating and sorting every pair — the gain is large whenever k is small relative to n·m.
Solution & live demo
Common pitfalls
Seeding every possible pair
for i in range(len(nums1)):
for j in range(len(nums2)):
heappush(heap, (...))for i in range(min(k, len(nums1))):
heappush(heap, (nums1[i] + nums2[0], i, 0))Materializing the Cartesian product defeats the output-sensitive advantage.
Advancing both indices
heappush(heap, (..., i + 1, j + 1))
heappush(heap, (..., i, j + 1))
Each heap entry belongs to one fixed nums1 row, whose next sum advances only in nums2.
Assuming k pairs always exist
while len(result) < k:
while heap and len(result) < k:
The Cartesian product may contain fewer than k pairs.
Edge cases
Return an empty list before reading the first element of nums2.
The loop ends when the heap becomes empty and returns every available pair.
Index-based heap entries preserve each distinct pair occurrence.