Find K Pairs with Smallest Sums

Given two sorted arrays, return the k pairs (u, v) with the smallest sums u + v, in non-decreasing order of sum. If fewer than k pairs exist, return all of them.

Why this is worth learning

Each first-array index defines a sorted row of pair sums as the second index increases. The heap merges these sorted rows by keeping only the next unreported pair from each active row.

Before coding: one-minute experiment

For A=[1,1] and B=[2,2], how many index pairs exist, and may the output contain four identical [1,2] rows?

Function signature

func KSmallestPairs(nums1, nums2 []int, k int) [][]int

Inputs / outputs

• nums1, nums2: sorted integer arrays.
• k: number of pairs to return.
• Return: up to k pairs with smallest sums.

Example

nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]

Constraints

• 0 <= len(nums1), len(nums2) <= 100_000

Core idea (near-solution)

Enumerating and sorting the Cartesian product costs space proportional to len(nums1)*len(nums2), even if only a few pairs are requested. Fixing the first index reveals sorted rows as the second index advances. Each row’s head dominates its hidden suffix, so the heap needs only one pending pair per active row. This turns an enormous candidate grid into a merge of sorted streams; the rank proof below justifies limiting the seeded rows.

Treat each nums1[i] as starting a sorted list of pairs with nums2. Use a min-heap over indices to always extract the next smallest sum.

Invariant: the heap contains the smallest unseen pair for each active i.

Algorithm (step-by-step)

1. If either array is empty or k == 0, return empty.
2. Push pairs (i, 0) for i = 0..min(k, len(nums1))-1 into a min-heap keyed by sum.
3. While heap not empty and result size < k:
   • Pop the smallest (i, j) and append [nums1[i], nums2[j]].
   • If j+1 < len(nums2), push (i, j+1).
4. Return the result list.

Correctness sketch

For each seeded row i, its current head is the least unreported pair in that row. Popping the smallest head is globally safe because all later entries in every active row are at least their heads. After outputting (i,j), insert (i,j+1) to restore that invariant. Seeding only min(k,len(nums1)) rows is sufficient: every omitted row’s first sum is at least the first sums of k earlier rows, so it cannot be strictly required before k outputs; ties allow alternative valid pairs. Index pairs, not value pairs, are the distinct candidates, so repeated input values legitimately produce duplicate value rows. Wide sum comparison prevents overflow from reversing heap order.

Trace (hand walkthrough)

Example input:
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]

Walk:
- init heap with (1,2),(7,2),(11,2)
- pop (1,2) -> add pair [1,2], push (1,4)
- pop (1,4) -> add [1,4], push (1,6)
- pop (1,6) -> add [1,6] (k=3 reached)

Pitfalls to avoid

• Generating all len(nums1)*len(nums2) pairs (too slow).
• Forgetting to limit initial heap size by k.
• Returning pairs out of sum order.

Debugging lens

Check nondecreasing mathematical sums, available pair multiplicities, and the cutoff sum. Do not require one ordering among equal-sum pairs. The corrected reference compares full signed sums even when a+b cannot fit in int.

Complexity

Let h=min(k,len(nums1)) and c=min(k,len(nums1)*len(nums2)), with nonnegative k. Time O((h+c) log(h+1)), including heap seeding, and auxiliary heap space O(h), excluding O(c) output. Empty inputs or k=0 return immediately.

Implementation notes (Go)

• Implement a min-heap of (sum, i, j) using container/heap.
• Compare mathematical sums without signed wraparound. Two full-width ints can need one extra sum bit; the reference stores a signed high word and unsigned low word. Plain a+b and int64(a)+int64(b) are both insufficient on a 64-bit int target.

Contract precision

k is nonnegative. Pairs are ranked by mathematical sums, returned in nondecreasing sum order, with no fixed tie order. The input arrays are read-only. Duplicate value pairs retain the multiplicity of distinct index pairs.

Reconstruction checkpoint

For A=[1,1] and B=[2,2], how many index pairs exist, and may the output contain four identical [1,2] rows?

Return to Heap / Priority Queue · Module quiz