Given two sorted arrays and k, return the k pairs (u, v), with u from the first array and v from the second, that have the smallest sums.
Before you code
There are m × n pairs; generating them all is wasteful. For a fixed u = nums1[i], the pairs (i, 0), (i, 1), … are already sorted by sum. That makes m sorted streams, and you need the first k items of their merge.
Hints
- Push
(nums1[i] + nums2[0], i, 0)for the first min(k, m) values of i. - Pop the smallest, record it, and push
(i, j + 1)if it exists. - Stop after k pops. The heap never holds more than min(k, m) entries.
Production & complexity notes
When solving Find k pairs with smallest sums on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Top-k and merging streams to reinforce the underlying pattern.
What it practices
Seeing a merge in a problem that doesn't mention lists, from Top-k and merging streams.