MediumArrayHeap (Priority Queue)

Find K Pairs with Smallest Sums

1 approach, code in every language

You are given two integer arrays sorted in non-decreasing order, nums1 and nums2, along with an integer k. A pair (u, v) is formed by taking one element u from nums1 and one element v from nums2.

Return the k pairs whose sums u + v are the smallest among all possible pairs.

Example 1

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

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

The three smallest sums are 1+2=3, 1+4=5, and 1+6=7, all pairing the smallest value of nums1.

Example 2

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

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

Both 1s in nums1 pair with the leading 1 in nums2 to give sum 2, the two smallest sums.

Constraints

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

Min-Heap Over Row Frontier

Seed a min-heap with pairs (nums1[i], nums2[0]); repeatedly pop the smallest and push the next pair along that row.

Loading animation…

Intuition

Because both arrays are sorted, the smallest possible sum is nums1[0] + nums2[0]. From any pair (i, j), the next candidates in increasing sum are (i+1, j) and (i, j+1), but exploring both explodes into duplicates. A cleaner frontier seeds the heap with the first column only: (i, 0) for each i. Popping the minimum yields the next smallest pair, and pushing (i, j+1) advances that row's pointer. This performs at most k pops, each touching one new candidate, so the heap never exceeds the number of seeded rows.

Algorithm walkthrough

1If either array is empty, return an empty list.
2Push (nums1[i], nums2[0]) for i from 0 to min(k, len(nums1)) - 1 into a min-heap keyed by the pair sum.
3Pop the smallest pair and append (nums1[i], nums2[j]) to the answer.
4If j + 1 is within nums2, push (nums1[i], nums2[j+1]) to extend that row.
5Repeat until k pairs are collected or the heap empties.

Implementation

import heapq


class Solution:
    def kSmallestPairs(self, nums1: list[int], nums2: list[int], k: int) -> list[list[int]]:
        if not nums1 or not nums2:
            return []
        heap: list[tuple[int, int, int]] = []
        for i in range(min(k, len(nums1))):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
        result: list[list[int]] = []
        while heap and len(result) < k:
            _, i, j = heapq.heappop(heap)
            result.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
        return result

Time

O(k log k)

Space

O(k)

The heap is seeded with at most min(k, len(nums1)) entries and each of the k pops pushes at most one new pair, so its size stays bounded by k.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Smallest Coupled Trims is our own problem on the technique behind Find K Pairs with Smallest Sums: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free