Find K Pairs with Smallest Sums
Understanding the Problem
We have two sorted arrays and we need to find the k pairs (one element from each array) that produce the smallest sums. One option is to generate every possible pair, sort them by sum, and take the first k. With arrays up to 10^5 elements each, that means up to 10^10 pairs, far too many to enumerate.
The sorted order of both arrays is what we exploit. The pair (nums1[0], nums2[0]) has the smallest sum. The second smallest sum must be either (nums1[1], nums2[0]) or (nums1[0], nums2[1]), because any other pair has both indices at least as large, so a larger or equal sum. Expanding outward from the minimum this way lets us pull pairs in sum order without touching all of them.
Key Constraints:
1 <= nums1.length, nums2.length <= 10^5→ Up to 10^10 total pairs. We cannot enumerate all pairs, so we need to find the k smallest without generating the rest.1 <= k <= 10^4→ k is small compared to the total number of pairs, so we only need to explore a small fraction of the pair space.- Both arrays are sorted → the property we exploit. Pairs with smaller indices have smaller or equal sums, so we can explore them in sum order.
-10^9 <= nums1[i], nums2[j] <= 10^9→ A single sum ranges from -210^9 to 210^9, which fits a signed 32-bit integer. The difference of two sums can reach 4*10^9, which does not, so a comparator must compare sums rather than subtract them.
Approach 1: Brute Force (Generate All Pairs)
Intuition
Generate every possible pair, compute its sum, sort all pairs by sum, and take the first k. This ignores the sorted order of the inputs and treats the problem as a generic "find the k smallest" over the full set of pairs.
Algorithm
- Create an empty list to store all pairs.
- For each element
nums1[i], pair it with every elementnums2[j]. - Sort all pairs by their sum.
- Return the first
kpairs from the sorted list.
Example Walkthrough
Code
- Time Complexity: O(m n log(m n)). We generate all m n pairs, then sort them. With m and n up to 10^5, this could be 10^10 pairs, which is way too slow.
- Space Complexity: O(m * n). We store every pair in memory, up to 10^10 entries.
This generates all m * n pairs even though we only need k of them. The next approach uses the sorted order to explore pairs in sum order and stop after finding k.
Approach 2: Min-Heap (Optimal)
Intuition
Lay the pairs out as a matrix where cell (i, j) holds the sum nums1[i] + nums2[j]. Because both arrays are sorted, each row increases left to right and each column increases top to bottom. The smallest value sits at (0, 0), and after picking it the next smallest is either (1, 0) or (0, 1).
This is the same structure as merging k sorted lists. Each row i is a sorted list of sums: nums1[i] + nums2[0], nums1[i] + nums2[1], nums1[i] + nums2[2], and so on. We merge these lists with a min-heap and pull the k smallest elements.
To generate each pair exactly once, seed the heap with the first element of each row, the pairs (i, 0), and when a pair (i, j) is popped, push only (i, j+1). Each row starts at column 0 and advances one column at a time, so no pair can be pushed twice.
Seeding stops at min(k, len(nums1)) rows. The k smallest pairs can come from at most k distinct rows, so rows beyond the first k never contribute.
Algorithm
- Initialize a min-heap. Push
(nums1[i] + nums2[0], i, 0)forifrom0tomin(k, len(nums1)) - 1. - Initialize an empty result list.
- While the result has fewer than
kpairs and the heap is not empty: - Pop the smallest sum pair
(sum, i, j)from the heap. - Add
[nums1[i], nums2[j]]to the result. - If
j + 1 < len(nums2), push(nums1[i] + nums2[j+1], i, j+1)into the heap. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(k * log(min(k, m))). We perform k pop operations from a heap of size at most min(k, m), where m = len(nums1). Each pop and push is O(log(min(k, m))).
- Space Complexity: O(min(k, m)). The heap holds at most min(k, m) elements at any time.