The Runtime Theory
mediumLeetCode#heap#sorted-arrays

Find K Pairs with Smallest Sums

Return k pairs drawn from two sorted arrays with the smallest pair sums.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innums1=[1,7,11], nums2=[2,4,6], k=3

out[[1,2],[1,4],[1,6]]

innums1=[1,1,2], nums2=[1,2,3], k=2

outtwo pairs with sum 2

innums1=[1,2], nums2=[3], k=3

out[[1,3],[2,3]]

Return k pairs drawn from two sorted arrays with the smallest pair sums.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain time and space costs in terms of input size and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs.

Reasoning prompt

Explore only a heap frontier rather than the full Cartesian product; prevent duplicate index pairs.

Use the linked judge for the canonical challenge. The examples above are compact TRT checks; create additional tests around the boundary most likely to break your invariant.

More practice in this topic

hard · heapFind Median from Data Streammedium · heapK Closest Points to Originmedium · heapKth Largest Element in an Array

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save