Find K Pairs with Smallest Sums
Last Updated: April 4, 2026
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. The naive reaction is to generate every possible pair, sort them by sum, and take the first k. But with arrays up to 10^5 elements each, that would mean up to 10^10 pairs, which is way too many.
The sorted order of both arrays is the critical detail here. Since both arrays are sorted, the pair (nums1[0], nums2[0]) is guaranteed to have the smallest sum. The second smallest sum must be either (nums1[1], nums2[0]) or (nums1[0], nums2[1]). This pattern of "expanding from the minimum" is exactly what a min-heap handles well. We don't need to look at all pairs, just the ones that could possibly be the next smallest.
Key Constraints:
1 <= nums1.length, nums2.length <= 10^5→ Up to 10^10 total pairs. We absolutely cannot enumerate all pairs. We need a way to find the k smallest without generating the rest.1 <= k <= 10^4→ k is relatively small compared to the total number of pairs. This means we only need to explore a tiny fraction of the pair space.- Both arrays are sorted → This is the key property to exploit. Pairs involving smaller indices tend to have smaller sums, so we can explore them in order.
-10^9 <= nums1[i], nums2[j] <= 10^9→ Sums can range from -210^9 to 210^9. Use long/int64 if needed to avoid overflow in some languages.
Approach 1: Brute Force (Generate All Pairs)
Intuition
The most straightforward approach: generate every possible pair, calculate their sums, sort all pairs by sum, and take the first k. This is the natural "try everything" starting point.
Since both arrays are sorted, we know the pairs exist. We just need to find the k smallest. The brute force way is to not leverage the sorted property at all, treat it as a general "find top k" problem.
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.
We're generating all m * n pairs even though we only need k of them. Both arrays are sorted, so can we explore pairs in sum order and stop after finding k?
Approach 2: Min-Heap (Optimal)
Intuition
Here's the key insight: think of this as a grid problem. If we lay out a matrix where cell (i, j) represents the sum nums1[i] + nums2[j], both rows and columns are sorted. The smallest value is always at (0, 0). Once we pick (0, 0), the next smallest must be either (1, 0) or (0, 1).
This is exactly the same pattern as "merge k sorted lists." Each row i in the matrix forms a sorted list: nums1[i] + nums2[0], nums1[i] + nums2[1], nums1[i] + nums2[2], ... We're merging these sorted lists and pulling the k smallest elements.
The trick to avoid duplicates is this: seed the min-heap with the first element from each "list" (i.e., (i, 0) for each row i), and when we pop a pair (i, j), we only push (i, j+1). Since we only move forward in nums2 for a given nums1 index, every pair is generated exactly once.
We also cap the initial seeding at min(k, len(nums1)) rows, because we'll never need more than k pairs total, so there's no point starting with more than k rows.
The min-heap approach works because it mirrors the structure of the problem. Both arrays are sorted, so the sums form a matrix where values increase going right or down. By seeding the heap with the first column (the smallest sum in each row) and expanding rightward only when a pair is popped, we explore the matrix in sum order without ever generating pairs we don't need.
The "no duplicates" guarantee comes from the expansion rule: we only push (i, j+1) when (i, j) is popped. Since each row starts at column 0 and moves strictly forward, every (i, j) pair enters the heap at most once.
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:
a. Pop the smallest sum pair (sum, i, j) from the heap.
b. Add [nums1[i], nums2[j]] to the result.
c. 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.