A catalog team is given two already-sorted price lists — base SKUs in nums1, add-on fees in nums2, both ascending. Merchandising wants the k cheapest bundles: one SKU plus one add-on. The intern nested two loops, dumped every (u, v), sorted by sum, and sliced the first k. A handful of SKUs painted instantly. A catalog of tens of thousands of SKUs times a few hundred add-ons was still ranking pairs nobody would pick.

The k smallest pair sums means k pairs (u, v) with u from nums1 and v from nums2, not a ranking of every pair. Each nums1[i] paired with nums2 in increasing j is a sorted list. A heap of those current heads is the same “heap of fronts” as Merge K Sorted Lists. This is an interview writeup, not a heap lecture. That post owns sift. Here we only care about seed every (i, 0), poll the smallest, offer (i, j+1).

K Closest Points to Origin is the other polarity: a size-k heap that evicts losers. This prompt emits the next-smallest pair k times. Same k-way next-smallest as merge-k, different payload.

The problem

Given two arrays nums1 and nums2, both sorted ascending, and an int k, return k pairs (u, v) — u from nums1, v from nums2 — whose sums are the k smallest. Order among those k pairs does not matter.

nums1 = [2, 5, 9], nums2 = [1, 4, 8], k = 3  →  [[2, 1], [5, 1], [2, 4]]
nums1 = [4, 7],    nums2 = [3],       k = 5  →  [[4, 3], [7, 3]]
nums1 = [6],       nums2 = [2, 10],   k = 1  →  [[6, 2]]

First row: sums 3, then 6 and 6. [[2, 1], [2, 4], [5, 1]] is the same k. Second: k is larger than the pair count, so every pair comes back. Third: k is 1, so only the single smallest sum.

Note: You return the pairs, not the sums. Do not assume k is at most n1 * n2 — stop when the heap is empty. Empty inputs are usually out of scope; skip them unless they ask.

Generate every pair, then sort is the honest brute

Nested loops build every (u, v), sort by u + v, copy the first k. Correct, and slow when k is tiny next to n1 * n2. Do not sort by u then v — smallest pair sum is not “smallest first number.” You did not need a global sort of pairs that will never ship.

List<List<Integer>> kSmallestPairsBrute(int[] nums1, int[] nums2, int k) {
    List<int[]> pairs = new ArrayList<>();
    for (int u : nums1) {
        for (int v : nums2) {
            pairs.add(new int[] { u, v });
        }
    }
    pairs.sort((a, b) -> Integer.compare(a[0] + a[1], b[0] + b[1]));
    List<List<Integer>> answer = new ArrayList<>();
    for (int t = 0; t < k && t < pairs.size(); t++) {
        answer.add(List.of(pairs.get(t)[0], pairs.get(t)[1]));
    }
    return answer;
}

At a dozen SKUs this is a rounding error. In production you paid O(n1 n2 log(n1 n2)) to rank every bundle: which k pairs won? Both arrays were already sorted. You only needed the next-smallest head of k sorted pair-lists.

Note: The sort mutates the pair list you just built, not nums1 or nums2. Fine for a throwaway brute. The heap walk leaves the inputs alone and still returns the k winners.

Seed (i, 0), then only expand j + 1

Think of nums1[i] as the head of a sorted list of pairs (nums1[i], nums2[0]), (nums1[i], nums2[1]), … . Seed a min-heap with (i, 0) for each i in 0 .. min(k, nums1.length) - 1. Java’s PriorityQueue is a min-heap; the comparator reads nums1[i] + nums2[j], so poll is the current smallest front.

  • Poll (i, j), append (nums1[i], nums2[j]).
  • If j + 1 is in range, offer (i, j + 1). That list’s next pair re-enters the heap.
  • Repeat until you have k pairs, or the heap is empty.

You never generate every pair. You never mark (i, j) visited. Heap size stays O(min(k, n1)) entries of the form (i, j).

Walk [2, 5, 9] against [1, 4, 8] with k = 3. Heap entries are indices; s is the pair sum:

seed (i, 0):  heap [(0,0) s=3, (1,0) s=6, (2,0) s=10]

poll (0,0)  pair (2, 1)  offer (0,1) s=6     answer [(2, 1)]
              heap [(1,0) s=6, (0,1) s=6, (2,0) s=10]
poll (1,0)  pair (5, 1)  offer (1,1) s=9     answer [(2, 1), (5, 1)]
              heap [(0,1) s=6, (2,0) s=10, (1,1) s=9]
poll (0,1)  pair (2, 4)  offer (0,2) s=10    answer [(2, 1), (5, 1), (2, 4)]

size == k, stop

(1,0) and (0,1) both sum to 6; either poll order is fine. If k were 4, the next poll would be (1,1) at sum 9 — pair (5, 4) — not (2,0) or (0,2) at 10. The Java is that walk:

List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<List<Integer>> answer = new ArrayList<>();
    PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(nums1[a[0]] + nums2[a[1]], nums1[b[0]] + nums2[b[1]]));
    int n1 = nums1.length, n2 = nums2.length;
    for (int i = 0; i < n1 && i < k; i++) {
        heap.offer(new int[] { i, 0 });
    }
    while (!heap.isEmpty() && answer.size() < k) {
        int[] ij = heap.poll();
        int i = ij[0], j = ij[1];
        answer.add(List.of(nums1[i], nums2[j]));
        if (j + 1 < n2) {
            heap.offer(new int[] { i, j + 1 });
        }
    }
    return answer;
}

Time is O(k log min(k, n1)) — at most k polls and k offers, heap size at most min(k, n1). Space is O(min(k, n1)) besides the answer. Brute is O(n1 n2 log(n1 n2)) and ranks losers. Do not re-lecture sift at the whiteboard unless they ask.

Note: Why seed only min(k, n1) rows? nums1 is sorted, so the k pairs (nums1[0], nums2[0]) … (nums1[k-1], nums2[0]) already sit at or below (nums1[k], nums2[0]). You do not need that extra list.

Note: Do not expand both (i+1, j) and (i, j+1) from (0, 0) without a seen-set. (1, 1) is reachable from two parents, so the same pair re-enters the heap unless you mark visited. Seeding one axis and offering only j + 1 never duplicates. Same k-way shape as merge k sorted lists; a size-k eviction heap like k closest points is the wrong polarity.

What interviewers usually poke next

  • k = 1. Return (nums1[0], nums2[0]). Seeding one (0, 0) and polling once is the same idea with extra ceremony; say you noticed.
  • k larger than n1 * n2. The while already stops when the heap is empty. You return every pair. No extra cap.
  • Why not generate all pairs. Correct answers, O(n1 n2) pairs, a full sort. Fine at a dozen SKUs. Wrong bill when k is tiny next to the product.
  • Seen-set from (0, 0). Offer both neighbors, mark (i, j) visited. Works, wastes a HashSet, and the heap can hold more than O(k) candidates. One-axis seed is the cleaner board answer.
  • Merge k sorted lists. Each nums1[i] × nums2[j++] is a sorted list; the heap holds current fronts. Name that analogy. Do not re-solve merge k here.
  • Integer overflow on the sum. Board default is Integer.compare of the two int sums. A follow-up can widen: Long.compare((long) nums1[a[0]] + nums2[a[1]], …).
  • Design Twitter later. Same heap-of-k-heads merge, tweet timestamps instead of pair sums. Pre-assigned; do not write it on this board.

You are done with this problem when you can walk [2, 5, 9] against [1, 4, 8] for k = 3 without a seen-set, and you can say why seeding (i, 0) then offering only (i, j + 1) is merge-k on sorted pair lists.