← DSA Atlas
Dedicated problem page · #373

Find K Pairs with Smallest Sums

MediumHeap and Priority Queuek-way merge with a heapMin-heap over a sorted-matrix frontier
Solve on LeetCode ↗
373
MediumHeap and Priority QueueMin-heap over a sorted-matrix frontierk-way merge with a heap

Find K Pairs with Smallest Sums

Given two integer arrays nums1 and nums2 sorted in ascending order and an integer k, find the k pairs (u, v) with u from nums1 and v from nums2 that have the smallest sums u + v. Return these k pairs.

Open official problem prompt ↗
In plain English

Produce the k pairs with the smallest sums, in ascending sum order, drawing one element from each sorted array without enumerating every possible pair.

Picture it like this

Think of merging k sorted queues. Each row i of nums1 fixed against nums2 is its own increasing queue of sums. A single min-heap peeks at the front of every queue and always serves the globally smallest, advancing only that queue.

Example
Input
nums1 = [1, 7, 11], nums2 = [2, 4, 6], k = 3
Output
[[1, 2], [1, 4], [1, 6]]
Why
The three smallest pair sums are 1+2=3, 1+4=5, and 1+6=7; all other pairs sum to at least 9.
Constraints
1 <= nums1.length, nums2.length <= 10^5-10^9 <= nums1[i], nums2[i] <= 10^9nums1 and nums2 are sorted ascending1 <= k <= 10^4
Pattern lesson

See the pattern, then code

k-way merge with a heap
Recognition clue

Smallest combinations drawn from two (or more) sorted sequences is the k-way merge signal: explore candidates in sum order using a heap rather than generating all pairs.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. Treat the pairs as a sorted grid: (i, j) has sum nums1[i]+nums2[j], increasing down rows and across columns. The next-smallest pair is always adjacent to one already taken, so a min-heap of frontier pairs yields them in order without materializing the whole grid.

New words, made simpleKnow these before the algorithm
Frontier
The set of next-unexplored candidate pairs sitting at the edge of what has been taken.
k-way merge
Merging several sorted sequences into one order by repeatedly taking the smallest available head.
Tuple key
Storing (sum, i, j) so the heap orders by sum while remembering which indices produced it.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force all pairs

Generates far more pairs than needed; blows up when the arrays are large.

Form every pair, sort by sum, take the first k.

Time O(m*n log(m*n))Space O(m*n)
Best choiceHeap frontier

Explores only the pairs it needs; scales with k, not with m*n.

Seed one pair per row, then always expand the smallest by advancing its column.

Time O(k log k)Space O(k)
The rule we keep true

Invariant

The heap always contains exactly one unexplored candidate for each row that has entered the frontier, so its minimum is the globally smallest pair not yet output.

Why this is correct

Reasoning

Because both arrays are sorted, a pair (i, j) can only be preceded in sum by pairs above it or to its left. Since every pair we output immediately pushes its right neighbor, and rows enter seeded at column 0, no smaller unseen pair can exist outside the heap when we pop.

The algorithm in three movesSay these aloud before coding
1Seed the heap with pairs (nums1[i], nums2[0]) for the first min(k, len(nums1)) rows

seed heap: (3,0,0),(9,1,0),(13,2,0)

2Pop the smallest-sum pair and record it

pop (3): res=[[1,2]], push (5,0,1)

3Push its right neighbor (same i, next j) back onto the heap

pop (5): res=[[1,2],[1,4]], push (7,0,2)

4Repeat until k pairs are collected or the heap empties

pop (7): res=[[1,2],[1,4],[1,6]] done

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
1+2=30
1+4=51
1+6=72
7+2=93
11+2=134
1 · Readrows 0,1,2 with col 0
2 · AskInitial frontier?
3 · Update stateheap = [(3,0,0),(9,1,0),(13,2,0)]
4 · ResultOne candidate per row.
Key takeaway

Frontier of candidate sums; the heap always surfaces the next smallest.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Guard empties

    If either array is empty there are no pairs to form.

  2. 2
    Lines 9-10Seed the frontier

    Only min(k, len(nums1)) rows can contribute to the k smallest, each paired with nums2[0], its smallest partner.

  3. 3
    Lines 12-14Pop and record

    The heap root is the next smallest sum; store the actual values, not the indices.

  4. 4
    Lines 15-16Advance the column

    Pushing (i, j+1) offers the only new candidate that could now be smallest for that row.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k larger than m*n (return all pairs)
  • One array of length 1
  • Arrays containing negative numbers
  • Duplicate values producing equal sums (ties are fine, any order among equal sums is accepted)
!

Common beginner mistakes

  • Seeding all m rows instead of min(k, m), wasting memory when nums1 is huge
  • Also pushing down a row (i+1) as well as across a column, which double-counts pairs — seeding all rows up front and advancing only columns avoids duplicates
  • Forgetting the j+1 bounds check and indexing past nums2
  • Storing sums but forgetting to output the original element pair
Check your understanding

Why is it enough to advance only the column (j -> j+1) after a pop, rather than also the row?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word#703Kth Largest Element in a StreamFixed-size min-heap (bounded top-k)