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.

Input: nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3   → [[1,2],[1,4],[1,6]]
Input: nums1 = [1, 1, 2], nums2 = [1, 2, 3], k = 2   → [[1,1],[1,1]]
Input: nums1 = [1, 2], nums2 = [3], k = 3   → [[1,3],[2,3]]

Solution

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=[1,7,11], nums2=[2,4,6], K=3: seed [(3,0,0),(9,1,0),(13,2,0)]. Pop (3,0,0) -> [1,2], push (5,0,1). Pop (5,0,1) -> [1,4], push (7,0,2). Pop (7,0,2) -> [1,6]. Result [[1,2],[1,4],[1,6]].

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.