Find K Pairs with Smallest Sums

Find K Pairs with Smallest Sums

What is this problem about?

The Find K Pairs with Smallest Sums interview question asks you to find $k$ pairs of numbers $(u, v)$ such that $u$ is from a sorted array nums1 and $v$ is from a sorted array nums2. The pairs should be selected to have the smallest possible sums. You need to return these $k$ pairs as a list of lists.

Why is this asked in interviews?

This is a high-signal problem for companies like Amazon, Meta, and Google. It tests your ability to handle multiple sorted streams and optimize a selection process. While you could generate all $N imes M$ pairs and sort them ($O(NM \log(NM))$), the requirement is to find only $k$ pairs efficiently. It evaluations your mastery of the Heap (Priority Queue) interview pattern, specifically for merging sorted lists.

Algorithmic pattern used

This problem uses a Min-Heap (Priority Queue).

1. Since the arrays are sorted, the smallest possible pair is always (nums1[0], nums2[0]).
2. Initialize a Min-Heap with pairs (nums1[i], nums2[0]) for all $i$ up to $\min(k, n1)$.
3. For $k$ iterations:
   • Pop the pair with the smallest sum from the heap.
   • Add it to the result list.
   • If the popped pair was (nums1[i], nums2[j]) and $j+1 < n2$, push the next possible pair from that row (nums1[i], nums2[j+1]) into the heap. This ensures you only explore the most promising candidates at each step.

Example explanation

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

1. Heap: {(1+2, 0, 0), (7+2, 1, 0), (11+2, 2, 0)}.
2. Pop (1, 2). Result: [[1, 2]]. Add next: (1, 4).
3. Heap: {(1+4, 0, 1), (7+2, 1, 0), (11+2, 2, 0)}.
4. Pop (1, 4). Result: [[1, 2], [1, 4]]. Add next: (1, 6).
5. Heap: {(1+6, 0, 2), (7+2, 1, 0), (11+2, 2, 0)}.
6. Pop (1, 6). Result: [[1, 2], [1, 4], [1, 6]]. Finished $k=3$ pairs.

Common mistakes candidates make

• Brute Force: Generating all $N imes M$ pairs, which leads to Memory Limit Exceeded for large inputs.
• Wrong Heap Initialization: Pushing only one pair initially, which can lead to missing better candidates from other "rows" of the pairing matrix.
• Duplicate tracking: Using a Visited set for indices, which is $O(k)$ extra space and unnecessary if you follow the "row-based" insertion logic.

Interview preparation tip

Think of this as "Merging $k$ Sorted Lists." Each element in nums1 starts a sorted list of pairs with nums2. Using a Min-Heap to find the smallest element across multiple sorted streams is a universal pattern for top-K problems.