Find K pairs with smallest sums

Merge two sorted arrays to extract the k smallest pair sums using a heap.

heap priority queue two-sum k-smallest

Write a function `k_smallest_pairs(nums1, nums2, k)` that returns a list of the `k` pairs `(u, v)` with the smallest sums, where `u` comes from `nums1` and `v` comes from `nums2`. Both input lists are sorted in non-decreasing order. A pair is represented as a list `[u, v]`.

Return the pairs in order of their sums (smallest to largest). If two pairs have the same sum, you may return them in any relative order — the judge will accept any valid ordering as long as the set of pairs and their order by sum is correct. If there are fewer than `k` possible pairs, return all of them.

Use a heap-based approach for efficiency. The function should not modify the input lists.

Constraints

0 ≤ len(nums1), len(nums2) ≤ 500
1 ≤ k ≤ 5000 (if both arrays are empty, k can be 0)
-10^9 ≤ nums1[i], nums2[j] ≤ 10^9
Expected time complexity: O(k log k) or better.

Example

# Example 1
>>> k_smallest_pairs([1,7,11], [2,4,6], 3)
[[1,2],[1,4],[1,6]]

# Example 2
>>> k_smallest_pairs([1,1,2], [1,2,3], 2)
[[1,1],[1,1]]

# Example 3
>>> k_smallest_pairs([], [1,2,3], 3)
[]

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the pairs as an implicit matrix where rows are nums1 and columns are nums2. The top-left cell is always the smallest.

Use a min-heap to always pop the current smallest pair sum and push the next candidate(s) from the same row.

To avoid duplicates, push the right neighbor from each row only when you pop the leftmost element of that row.

Stop when you’ve collected k pairs or the heap is empty.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.