Find K Pairs with Smallest Sums — Medium Problem & Solution
Two arrays sorted in non-decreasing order are given. A pair [u, v] takes one number from each.
- Difficulty: Medium
- Topics: Arrays, Heap
- Asked at: Amazon, Google, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays sorted in non-decreasing order are given. A pair [u, v] takes one number from each.
Return the k pairs with the smallest sums, ordered by sum ascending; ties are broken by the smaller u, then the smaller v. If fewer than k pairs exist, return all of them.
Example 1
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]Example 2
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: Both 1s in `nums1` pair with the 1 in `nums2`.Example 3
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: Only two pairs exist.Constraints
1 <= nums1.length, nums2.length <= 1000-10^9 <= nums1[i], nums2[i] <= 10^9nums1 and nums2 are sorted in non-decreasing order.1 <= k <= 1000The pairs are returned sorted by sum, then by u, then by v.
How to solve Find K Pairs with Smallest Sums
Keep a frontier of candidate pairs in a min-heap. Both arrays are sorted, so the next-smallest pair is always one step to the right of a pair already taken.
Approach
- Push
[i, 0]for the firstmin(n, k)rows — no more can ever be needed. - Pop the smallest, record
[nums1[i], nums2[j]]. - Push
[i, j + 1]if that column exists. - Stop after
kpops or when the heap empties.
Why it works
Only min(n, k) rows need seeding, because the answer can hold at most k pairs and each row contributes its smallest first. Ordering the heap on (sum, u, v) rather than the sum alone is what makes the output deterministic — without it, equal sums could come out in any order and two correct implementations would disagree.
Complexity
- Time —
O(k log k) - Space —
O(k)
Pitfalls
- Seeding every row is wasteful when
nfar exceedsk. - Pushing both
[i+1, j]and[i, j+1]duplicates pairs unless visits are tracked. - Fewer than
kpairs may exist; the loop must also stop on an empty heap.
Reference solution
Python
from typing import List
import heapq
def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
n, m = len(nums1), len(nums2)
heap = []
for i in range(min(n, k)):
heapq.heappush(heap, (nums1[i] + nums2[0], nums1[i], nums2[0], i, 0))
out = []
while len(out) < k and heap:
_, u, v, i, j = heapq.heappop(heap)
out.append([u, v])
if j + 1 < m:
heapq.heappush(heap, (nums1[i] + nums2[j + 1], nums1[i], nums2[j + 1], i, j + 1))
return outJavaScript
var kSmallestPairs = function(nums1, nums2, k) {
var n = nums1.length, m = nums2.length;
var heap = [];
var less = function(a, b) {
var sa = nums1[a[0]] + nums2[a[1]], sb = nums1[b[0]] + nums2[b[1]];
if (sa !== sb) return sa < sb;
if (nums1[a[0]] !== nums1[b[0]]) return nums1[a[0]] < nums1[b[0]];
return nums2[a[1]] < nums2[b[1]];
};
var push = function(v) {
heap.push(v);
var i = heap.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (!less(heap[i], heap[p])) break;
var t = heap[p]; heap[p] = heap[i]; heap[i] = t;
i = p;
}
};
var pop = function() {
var top = heap[0];
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var i = 0;
for (;;) {
var l = 2 * i + 1, r = l + 1, s = i;
if (l < heap.length && less(heap[l], heap[s])) s = l;
if (r < heap.length && less(heap[r], heap[s])) s = r;
if (s === i) break;
var t = heap[s]; heap[s] = heap[i]; heap[i] = t;
i = s;
}
}
return top;
};
var limit = Math.min(n, k);
for (var i2 = 0; i2 < limit; i2++) push([i2, 0]);
var out = [];
while (out.length < k && heap.length > 0) {
var cur = pop();
out.push([nums1[cur[0]], nums2[cur[1]]]);
if (cur[1] + 1 < m) push([cur[0], cur[1] + 1]);
}
return out;
};Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.