Coding Interview PatternsFind K Pairs with Smallest Sums
MediumK-way Merge

Find K Pairs with Smallest Sums

Explanation & Solution

Practice Problem

Description

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Examples

Input:nums1 = [1,7,11], nums2 = [2,4,6], k = 3
0
1
1
7
2
11
0
2
1
4
2
6

Output: [[1,2],[1,4],[1,6]]

Explanation: The first 3 pairs with smallest sums are: (1,2), (1,4), (1,6). All of them use the smallest element from nums1.

Input:nums1 = [1,1,2], nums2 = [1,2,3], k = 2
0
1
1
1
2
2
0
1
1
2
2
3

Output: [[1,1],[1,1]]

Explanation: The first 2 pairs with smallest sums are: (1,1) and (1,1). Both pairs use elements from both arrays that sum to 2.

Input:nums1 = [1,2], nums2 = [3], k = 3
0
1
1
2
0
3

Output: [[1,3],[2,3]]

Explanation: All possible pairs are (1,3) and (2,3). Only 2 pairs exist, so we return both even though k = 3.

Constraints

  • 1 <= nums1.length, nums2.length <= 10^5
  • -10^9 <= nums1[i], nums2[i] <= 10^9
  • nums1 and nums2 are sorted in non-decreasing order.
  • 1 <= k <= 10^4
  • k <= nums1.length * nums2.length

Approach

K-way Merge pattern

1. Understand the Pair Space

  • We have two sorted arrays and need to find k pairs with the smallest sums.
  • A brute-force approach would generate all pairs and sort — but that's O(m*n*log(m*n)) which is too slow.
  • Since both arrays are sorted, we can use a min-heap to efficiently explore pairs in order of their sum.

2. Initialize the Min-Heap

  • Start by pushing pairs (nums1[i], nums2[0]) for each index i in nums1 (up to k elements).
  • These represent the smallest possible sum for each row, since nums2 is sorted and nums2[0] is the smallest.
  • The heap stores tuples of [sum, i, j] where i and j are indices into nums1 and nums2.

3. Extract Pairs Greedily

  • Pop the minimum-sum pair from the heap and add it to the result.
  • For the popped pair at indices (i, j), the next candidate from the same row is (i, j+1) — push it onto the heap if j+1 is within bounds.
  • This works because for a given nums1[i], the sums nums1[i] + nums2[0], nums1[i] + nums2[1], ... are in increasing order.

4. Terminate When k Pairs Found

  • Repeat the extract-and-push process until we have collected k pairs or the heap is empty.
  • We never need to explore the entire pair space — only the k smallest sums.

Key Insight

By seeding the heap with the first column of the pair matrix and lazily expanding one column at a time, we only ever explore O(k) pairs. The min-heap ensures we always process the next smallest sum.

Time
O(k log k)at most k heap operations, each O(log k) since the heap never exceeds size k.
Space
O(k)for the heap and the result array.

Visualization

Input:
[1, 7, 11], k = 3
1071112
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Kth Smallest Element in a Sorted Matrix
Next
Smallest Range Covering Elements from K Lists