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.

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)

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

• Invariant: the heap contains the smallest unseen pair for each active i.
• The heap always maintains its ordering invariant.
• Pushing and popping preserves the set of best candidates so far.
• The final heap contents/top yields the correct answer.

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.

Complexity

• Time: O(k log min(k, len(nums1))).
• Extra space: O(min(k, len(nums1))) for the heap.

Implementation notes (Go)

• Implement a min-heap of (sum, i, j) using container/heap.
• Compute sums on the fly from indices to avoid extra storage.