Find K Pairs with Smallest Sums - Solution & Explanation

Problem Overview: You are given two sorted integer arrays and an integer k. The task is to return the k pairs (u, v) where u comes from the first array and v from the second, such that their sums are the smallest among all possible pairs.

Approach 1: Direct Pair Generation and Sorting (Time: O(m * n log(m * n)), Space: O(m * n))

The straightforward approach generates every possible pair from the two arrays. Iterate through both arrays, compute the sum for each pair, and store the pairs in a list. Sort the list based on the pair sum and return the first k elements. This method is easy to implement and clearly demonstrates the problem logic, but it becomes expensive when both arrays are large because the number of pairs is m * n. The sorting step dominates the runtime.

Approach 2: Min-Heap (Priority Queue) Expansion (Time: O(k log m), Space: O(m))

The optimal strategy uses a min-heap (priority queue) to always expand the next smallest pair. Since both arrays are sorted, the smallest pair involving nums2 for a fixed index i in nums1 starts with (i, 0). Push the first pair from each of the first min(m, k) elements of nums1 into the heap. Each heap entry stores indices and the current sum. Repeatedly pop the smallest pair, add it to the result, and push the next pair from the same row (i, j+1). This controlled expansion ensures you only explore pairs that could belong in the smallest k, avoiding the full m * n search space. The heap guarantees that the next extracted pair always has the smallest available sum.

Recommended for interviews: Interviewers expect the min-heap solution. The brute-force generation shows you understand the problem space, but the priority queue expansion demonstrates knowledge of ordered exploration and efficient use of a heap. It reduces work from potentially millions of pairs to only the k pairs that matter.