Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Both arrays are sorted ascending. The smallest possible sum is nums1[0]+nums2[0]. Seed a min-heap with the pairs (nums1[i], nums2[0]) for the first min(k, len(nums1)) rows, keyed by sum. Pop the smallest each time — that pair is the next answer — and push its right neighbour (i, j+1) in the same row. This expands only the frontier of candidates, giving O(k log k) instead of materialising all m·n sums.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you exploit the sorted structure to avoid generating all m·n sums, and whether you see the problem as a k-way merge driven by a min-heap on an expanding frontier.
Where candidates slip
Generating every pair and sorting (O(m·n log(m·n)) time and space), or pushing both (i+1,j) and (i,j+1) on each pop — which double-counts pairs and explodes the heap.
How to stand out
Call it a k-way merge: 'each row i is the sorted list nums1[i]+nums2[*]; I'm merging len(nums1) sorted lists and taking k heads.' Then justify pushing only the right neighbour to avoid duplicates.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSeed heap with (nums1[i]+nums2[0], i, 0) for first min(k, len) rowsCollected k pairs or heap empty?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Generate All Pairs and Sort
1Hint 1Explore hintHide hint
There are len(nums1) × len(nums2) possible pairs. What's the most direct way to find the k with the smallest sums?
2Hint 2Explore hintHide hint
Form every pair, sort all of them by sum, and take the first k.
3Hint 3Explore hintHide hint
This ignores that the arrays are sorted — note that as the inefficiency you'll fix next.
A · Core idea
The most literal reading: a pair is any (nums1[i], nums2[j]), there are m·n of them, so generate them all, sort by sum, and slice the first k.
Why it's correct. It enumerates the entire universe of pairs, so the k smallest sums are guaranteed to be in the sorted prefix. There is no cleverness to get wrong.
Why it throws away the gift. The problem hands us two sorted arrays and we ignore that entirely. Sorting m·n items when we only want k of them (and k ≤ 10⁴ ≪ m·n ≤ 10¹⁰) is enormously wasteful — we sort 10 billion sums to read off the first ten thousand.
Why we don't ship this. Beyond being slow, it's a memory bomb: storing m·n pairs blows the heap for large inputs. The fix is to never materialise pairs we don't need. Sortedness means the cheapest sums cluster in the top-left of the conceptual sum grid, and we can walk outward from there with a min-heap — the optimal approach.
When it's still acceptable. If both arrays are tiny (so m·n is small) or k is close to m·n, generate-and-sort is simpler and competitive. Mention that nuance; interviewers like calibrated answers.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums1 = [1,7,11], nums2 = [2,4,6], k = 3generate
all sums: 3,5,7, 9,11,13, 13,15,17
9 pairs built[[1,2],[1,4],[1,6]]C · Code with teaching comments
Reference implementation previewpublic List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { List<int[]> all = new ArrayList<>(); for (int x : nums1) { for (int y : nums2) { all.add(new int[]{x, y});Explore the full codeHide the full code
D · Why it works and complexityO(m·n log(m·n)) timeO(m·n) spaceOpen the invariant and proofExplore the proofHide the proof
Generating all pairs ignores that the smallest sums are concentrated near nums1[0]+nums2[0] because both arrays are sorted. Recognising that 'cheap sums live in the top-left corner of the grid' is the bridge to the heap solution.
ComplexityO(m·n log(m·n)) time, O(m·n) space — Building all m·n pairs is O(m·n); sorting them is O(m·n log(m·n)); both arrays up to 10⁵ make m·n up to 10¹⁰ pairs — infeasible in time and memory. But it's obviously correct.
E · Edge cases and pitfalls5nums1 = [1,2], nums2 = [3], k = 3 — Only 2 pairs exist; min(k, size) / slice returns both, no error.Explore edge casesHide edge cases
Edge cases handled
nums1 = [1,2], nums2 = [3], k = 3Only 2 pairs exist; min(k, size) / slice returns both, no error.Large m and nm·n can reach 10¹⁰ pairs — this approach runs out of memory/time. Motivates the heap.
Pitfalls
- Out-of-memory when m·n is large — the array of all pairs doesn't fit.
- Indexing all.get(k) without min(k, size) — IndexOutOfBounds when fewer than k pairs.
- Forgetting the arrays are sorted, so missing the far cheaper heap approach.
Approach 2 of 2 · Optimal
Min-Heap over the Sorted Frontier (Optimal)
1Hint 1Explore hintHide hint
Picture an m×n grid where cell (i,j) holds nums1[i]+nums2[j]. Because both arrays are sorted, sums increase going right and going down. Where is the smallest sum?
2Hint 2Explore hintHide hint
The smallest is the top-left (0,0). The next smallest must be a neighbour of cells already chosen — explore a frontier with a min-heap keyed by sum.
3Hint 3Explore hintHide hint
Seed the heap with column 0 of each row: (nums1[i]+nums2[0], i, 0). Pop the min, record the pair, and push (i, j+1). Repeat k times. Pushing only the right neighbour avoids duplicates because each row was seeded exactly once.
A · Core idea
Model the sums as an m × n grid: cell (i, j) is nums1[i] + nums2[j]. Because both arrays are sorted non-decreasingly, sums increase as you move right (larger nums2[j]) and as you move down (larger nums1[i]). The grid is monotone in both directions, so the cheapest sums hug the top-left corner.
Why seed one cell per row. Each row i is itself a sorted list: nums1[i]+nums2[0] ≤ nums1[i]+nums2[1] ≤ …. The whole problem is therefore a k-way merge of min(k, m) sorted lists, and the classic way to merge sorted lists is a min-heap seeded with each list's head. The head of row i is its column-0 cell (nums1[i]+nums2[0], i, 0). We only need min(k, m) rows because we'll emit at most k pairs and each emitted pair frees at most one new candidate.
Why we push only `(i, j+1)`, never `(i+1, j)`. This is the subtle correctness point. When we pop cell (i, j), the only new candidate it unlocks is its right neighbour (i, j+1) — the next-cheapest sum in the same row. We must not also push the down-neighbour (i+1, j), because row i+1 was already given its own seed at (i+1, 0) and will advance through its own columns independently. If we pushed both directions, cell (i+1, j) would be reachable from two paths — from (i, j) going down and from (i+1, j-1) going right — and we'd insert it twice, double-counting pairs and bloating the heap. Seeding rows once + advancing only rightward guarantees each cell enters the heap exactly once.
Why this is correct (the frontier argument). At any moment the heap contains the cheapest not-yet-emitted cell of every row that has been 'opened'. The global minimum among all un-emitted cells is therefore the heap's top — any cheaper cell would have to be the left neighbour of a heap entry, but that left neighbour was already emitted (which is exactly when we pushed the current entry). So popping the heap top always yields the next-smallest sum overall.
Cost and Python detail. We perform k cycles of pop + (maybe) push, each O(log(heap size)) and the heap never exceeds O(k) — so O(k log k), completely decoupled from the enormous m·n. Python's heapq is a min-heap and tuples compare lexicographically, so storing (sum, i, j) orders by sum automatically (with i, j as harmless tie-breakers). Java needs an explicit comparator on the sum.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums1 = [1,7,11], nums2 = [2,4,6], k = 3How to read it:Rows are pre-seeded at column 0, so going down is already covered; popping (i,j) only opens (i,j+1).
[[1,2],[1,4],[1,6]]C · Code with teaching comments
D · Why it works and complexityO(k log k) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
It's a k-way merge in disguise: each row is a sorted list, and the smallest sums form an expanding frontier from the top-left. Seeding each row once and advancing only rightward keeps every grid cell entering the heap exactly once — that single discipline is what prevents duplicates and keeps it O(k log k).
ComplexityO(k log k) time, O(k) space — The heap holds at most min(k, m) seeds plus one push per pop, so its size stays O(k). We do k pop+push cycles, each O(log k) → O(k log k) time, O(k) space. Independent of the (huge) m·n.
E · Edge cases and pitfalls7nums1 = [1,2], nums2 = [3], k = 3 — Seed (1,0) and (2,0); only 2 pairs total, heap drains after 2 pops, loop ends — returns both.Explore edge casesHide edge cases
Edge cases handled
nums1 = [1,2], nums2 = [3], k = 3Seed (1,0) and (2,0); only 2 pairs total, heap drains after 2 pops, loop ends — returns both.k larger than m·n`while min_heap` exits when the frontier is exhausted; result has all m·n pairs.Negative values, e.g. nums1 = [-5,-2], nums2 = [-3,0]Sums (-8, -5, -2, ...) still increase rightward/downward; frontier logic unaffected.
Pitfalls
- Pushing both (i+1, j) and (i, j+1) — double-counts cells and bloats the heap; only push (i, j+1).
- Seeding all m rows instead of min(k, m) — wasteful when m ≫ k.
- Forgetting the empty-input / k==0 guard — heap stays empty but indexing nums2[0] on an empty array throws.
- Storing only the sum without (i, j) — you can't recover the neighbour to push.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { List<List<Integer>> result = new ArrayList<>(); if (nums1.length == 0 || nums2.length == 0 || k == 0) { return result; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Pushing both neighbours (duplicates)
Cell (i+1, j) is reachable both from (i, j) going down and from (i+1, j-1) going right. Pushing both directions inserts it twice, double-counting pairs.
Explore the code comparisonHide the code comparison
Pushing both neighbours (duplicates)
Cell (i+1, j) is reachable both from (i, j) going down and from (i+1, j-1) going right. Pushing both directions inserts it twice, double-counting pairs.
Don't write this
_, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])
if i + 1 < len(nums1):
heapq.heappush(min_heap, (nums1[i+1] + nums2[j], i+1, j)) # BUG
if j + 1 < len(nums2):
heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))Write this instead
_, i, j = heapq.heappop(min_heap)
result.append([nums1[i], nums2[j]])
if j + 1 < len(nums2): # only the right neighbour; rows are pre-seeded
heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))2Seeding every row
With m up to 10⁵ but k only 10⁴, seeding all m rows wastes time and space. You never need more than k starting points.
Explore the code comparisonHide the code comparison
Seeding every row
With m up to 10⁵ but k only 10⁴, seeding all m rows wastes time and space. You never need more than k starting points.
Don't write this
for (int i = 0; i < nums1.length; i++) {
minHeap.offer(new int[]{i, 0});
}Write this instead
for (int i = 0; i < Math.min(nums1.length, k); i++) {
minHeap.offer(new int[]{i, 0});
}3Storing the sum but losing the indices
To push the right neighbour you need to know which row i and column j you popped. Storing only the sum makes that impossible.
Explore the code comparisonHide the code comparison
Storing the sum but losing the indices
To push the right neighbour you need to know which row i and column j you popped. Storing only the sum makes that impossible.
Don't write this
heapq.heappush(min_heap, nums1[i] + nums2[0]) # no i, j -- can't advanceWrite this instead
heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))Revise
Carry the pattern into the interview
Pattern to remember
Min-heap over a sorted grid frontier (k-way merge)
Code pattern to memorize
heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, len(nums1)))]
repeat k times:
(s, i, j) = heap.pop_min()
emit (nums1[i], nums2[j])
if j + 1 < len(nums2): heap.push((nums1[i] + nums2[j+1], i, j+1))Rules to remember
- 1Seed one entry per row, not the whole grid — start each row at its smallest column j=0.
- 2On popping
(i, j), push only(i, j+1)— the next-smallest in that row; never push(i+1, j)(its row was already seeded). - 3Cap the seed at min(k, len(nums1)) rows — you can never need more than k starting points.
- 4Store (sum, i, j) in the heap so it orders by sum and you can reconstruct both values and find the neighbour.
- 5Think of it as merging len(nums1) sorted lists (each row is sorted because nums2 is sorted) and taking the k smallest heads.
- 6Guard empty inputs and
k == 0up front — return an empty list.
Use this pattern when
- Two (or more) sorted sequences; you need the k smallest/largest combinations by some monotone cost
- Materialising all m·n combinations is too expensive but you only need a small k
- The cost grid is monotone along both axes (sorted rows AND columns)
- k-way merge of sorted lists, or 'kth smallest in a sorted matrix' flavored problems
Choose another pattern when
- You need ALL pairs, not just k → just double-loop, no heap benefit
- Inputs aren't sorted → sort first or the frontier logic breaks
- k is comparable to m·n → plain generate-and-sort is simpler and competitive
- Single array / no grid structure → a different selection technique
Interview takeaway
When two sorted arrays form a monotone sum grid, the k smallest sums live on an expanding frontier you can explore with a min-heap — exactly the k-way merge trick. Seed the cheapest cell of each row, and every pop reveals the next answer while pushing just its successor. The same frontier idea solves Kth Smallest in a Sorted Matrix and merging k sorted lists.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternMin-heap over a monotone sorted grid — the k-way merge frontier. Whenever sorted sequences induce a cost grid that's monotone along both axes and you need only the k cheapest combinations, seed each row's head and expand the frontier with a min-heap. Same shape as Kth Smallest in a Sorted Matrix and Merge k Sorted Lists.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kth Smallest Element in a Sorted MatrixComing soonSame monotone-grid frontier; min-heap from the top-left, or binary search on the value.
- Merge k Sorted ListsComing soonThe pure k-way merge this problem reduces to — min-heap over list heads.
- Smallest Range Covering Elements from K ListsComing soonMin-heap across k sorted lists tracking the current max — frontier over multiple sorted sequences.
- Kth Largest Element in an ArrayHeap-for-selection fundamentals that underpin all 'k smallest/largest' problems.