Mediumheap-top-k
Find K Pairs with Smallest Sums
Problem (restated)
Two sorted ascending arrays. Return k pairs (u,v) with u from nums1, v from nums2, with the smallest sums.
Intuition
Start with (nums1[i], nums2[0]) for i < k. Pop smallest sum; push next j+1 for same i.
Approaches
Min-heap over first column
Tested onlyTime O(k log k)Space O(k)
Idea. Avoid full n×m matrix. Heap expands along nums2 for the best rows only.
Walkthrough. [1,7,11]×[2,4,6], k=3 → [1,2],[1,4],[1,6].
Trade-offs. Sorted arrays are essential; without order fall back to full sort of pairs.
Solution
export function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
const res: number[][] = [];
if (!nums1.length || !nums2.length || k <= 0) return res;
// min-heap of [sum, i, j]
const heap: [number, number, number][] = [];
const push = (i: number, j: number) => {
heap.push([nums1[i]! + nums2[j]!, i, j]);
heap.sort((a, b) => a[0]! - b[0]!);
};
const n1 = Math.min(nums1.length, k);
for (let i = 0; i < n1; i++) push(i, 0);
while (k-- > 0 && heap.length) {
const [, i, j] = heap.shift()!;
res.push([nums1[i]!, nums2[j]!]);
if (j + 1 < nums2.length) push(i, j + 1);
}
return res;
}
export function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
const res: number[][] = [];
if (!nums1.length || !nums2.length || k <= 0) return res;
// min-heap of [sum, i, j]
const heap: [number, number, number][] = [];
const push = (i: number, j: number) => {
heap.push([nums1[i]! + nums2[j]!, i, j]);
heap.sort((a, b) => a[0]! - b[0]!);
};
const n1 = Math.min(nums1.length, k);
for (let i = 0; i < n1; i++) push(i, 0);
while (k-- > 0 && heap.length) {
const [, i, j] = heap.shift()!;
res.push([nums1[i]!, nums2[j]!]);
if (j + 1 < nums2.length) push(i, j + 1);
}
return res;
}
Template connection
Heap BFS over a sorted product space (k-way style).
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?