310. Find K Pairs with Smallest Sums
Your function receives two integer arrays nums1 and nums2, each sorted in non-decreasing order, and an integer k. A pair takes one value u from nums1 and one value v from nums2.
Return the k pairs with the smallest sums u + v, as a list of [u, v] pairs. Order the result by ascending sum; when two pairs tie on sum, put the one with the smaller nums1 value first. If the same pair of values can be formed multiple times (duplicates in the arrays), it appears in the result that many times.
You are guaranteed k never exceeds the total number of pairs. The full cross product can be huge — can you find the k winners without building it?
Example 1:
Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Output: [[1, 2], [1, 4], [1, 6]]
Explanation: The smallest sums are 1+2 = 3, 1+4 = 5, and 1+6 = 7 — every pair using 1 beats any pair using 7 or 11.
Example 2:
Input: nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2
Output: [[1, 1], [1, 1]]
Explanation: Both copies of 1 in nums1 pair with the 1 in nums2 for a sum of 2, so the pair [1, 1] legitimately appears twice.
Constraints:
- 1 ≤ nums1.length, nums2.length ≤ 200
- -10⁴ ≤ nums1[i], nums2[i] ≤ 10⁴
- nums1 and nums2 are sorted in non-decreasing order
- 1 ≤ k ≤ nums1.length * nums2.length
Hints:
Generating every pair, sorting by sum, and slicing off k works — but it materializes n1 × n2 pairs to keep only k of them.
Picture a grid where cell (i, j) holds nums1[i] + nums2[j]. Every row is sorted left to right and every column top to bottom. Where must the smallest unclaimed cell live?
Seed a min-heap with the first cell of the first min(k, n1) rows. Each time you pop (i, j), the only new candidate it unlocks is (i, j+1) — its right neighbor.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Expected output: [[1, 2], [1, 4], [1, 6]]