Problem Statement

Find K Pairs with Smallest Sums

You get two lists of numbers, nums1 and nums2. Both are already sorted from smallest to largest. You also get a number k. A "pair" means you pick one number from nums1 and one number from nums2, and the "sum" of a pair is those two numbers added together. Your job is to return the k pairs that have the smallest sums.

mediumHeapHeap / Priority QueueTime: O(k log k) · Space: O(k)

Signals to notice

k smallest pairs from two sorted arraysdon't enumerate all pairslazy expansion

Brute force first

Generate all n×m pairs, sort by sum, take first k. Creates every possible pair even though you only need k. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Min-heap starting with (nums1[0]+nums2[0], 0, 0). Pop the smallest, then push the next pair in each dimension. Like BFS on a 2D grid of sums — you only explore what's needed. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `nums1=[1,7,11], nums2=[2,4,6], k=3`

Seed heap with each nums1[i]+nums2[0]: heap=[(3,0,0),(9,1,0),(13,2,0)], result=[]
Pop (3,0,0) -> result=[[1,2]]; j+1=1<3 push (1+4,0,1)=(5,0,1); heap=[(5,0,1),(9,1,0),(13,2,0)]
Pop (5,0,1) -> result=[[1,2],[1,4]]; j+1=2<3 push (1+6,0,2)=(7,0,2); heap=[(7,0,2),(9,1,0),(13,2,0)]
Pop (7,0,2) -> result=[[1,2],[1,4],[1,6]]; j+1=3 not <3, no push; heap=[(9,1,0),(13,2,0)]
len(result)=3 == k -> stop loop
Return [[1,2],[1,4],[1,6]]

What must stay true

The heap always contains the frontier of unexplored pairs. The smallest unexplored sum is always on top. You never need to look beyond k expansions because each expansion considers the next cheapest neighbor. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

heap = min-heap of (nums1[i]+nums2[0], i, 0) for i in 0..min(len(nums1),k)
result = []
while heap and len(result) < k:
    s, i, j = pop-smallest(heap)
    result.append([nums1[i], nums2[j]])
    if j+1 < len(nums2): push(heap, (nums1[i]+nums2[j+1], i, j+1))
return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Pushing duplicate pairs — use a visited set or only expand in one direction per pop to avoid processing the same (i,j) pair twice. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Heap / Priority Queue Pattern