Find K Pairs with Smallest Sums

Problem

Recommendation systems match users to items using a combined score from two sorted feature arrays. Finding the K best-scoring pairs without materializing all n*m combinations is essential at scale. Given two sorted integer arrays in ascending order, find the k pairs (one element from each array) with the smallest sums. Return any k valid pairs.

Example 1:

Input: nums1 = [2, 8, 12], nums2 = [1, 3, 5], k = 3
Output: [[2,1],[2,3],[2,5]]
Explanation: the three pairs with the smallest sums, all pairing 2 with the smallest nums2 values.

Example 2:

Input: nums1 = [1, 1, 3], nums2 = [2, 4, 6], k = 2
Output: [[1,2],[1,2]]
Explanation: sum 3 is achievable twice, using each of the two 1s in nums1 with the 2 in nums2.

Example 3:

Input: nums1 = [3, 5], nums2 = [7], k = 3
Output: [[3,7],[5,7]]
Explanation: only two pairs exist, so both are returned even though k is 3.

Constraints:

• 1 <= nums1.length, nums2.length <= 10^3
• -100 <= nums1[i], nums2[i] <= 100
• nums1 and nums2 are sorted in ascending order.
• 1 <= k <= 10^3

Solution Breakdown

Approach: min-heap over sorted rows, expanding one column at a time.

Think of the pairs as a grid where row i pairs nums1[i] with each element of the sorted nums2. Within any row the sums only grow as j increases, so the smallest pair in row i is always (nums1[i] + nums2[0], i, 0). Seed the heap with that minimum from every row (capped at min(k, len(nums1)), since rows beyond K can never surface). Now repeatedly pop the global minimum (total, i, j), record the pair [nums1[i], nums2[j]], and push only that row's next candidate (nums1[i] + nums2[j+1], i, j+1) when j+1 is in range. Because every row contributes its current-best candidate to the heap and we only ever advance j from a popped entry, the pops come out in non-decreasing sum order and no (i, j) is ever pushed twice. This explores at most K columns instead of materializing all n*m pairs.

Trace nums1=[2,8,12], nums2=[1,3,5], K=3: seed [(3,0,0),(9,1,0),(13,2,0)]. Pop (3,0,0) -> [2,1], push (5,0,1). Pop (5,0,1) -> [2,3], push (7,0,2). Pop (7,0,2) -> [2,5]. Result [[2,1],[2,3],[2,5]].

Edge cases: an empty nums1 or nums2 returns early with []. When K exceeds the total pair count, the heap drains and the loop exits with every valid pair rather than padding to K.

Complexity: O((m + k) log k) time where m = len(nums1), O(min(k, m)) space - the heap never holds more than one entry per seeded row.