All problems

Find K Pairs with Smallest Sums

Medium · heap

You are given two lists of integers, nums1 and nums2, both sorted in ascending order, and an integer k.

A pair takes one number from each list: the number at position i of nums1 and the number at position j of nums2. Two pairs are different if their positions differ, even when their values are the same.

Return the k pairs with the smallest sums, as a list of [u, v] where u comes from nums1 and v from nums2. List them from the smallest sum to the largest. If two pairs have the same sum, the one with the smaller i comes first, and if i is also the same, the one with the smaller j.

If there are fewer than k pairs in total, return all of them in that order.

Examples

Example 1

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

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

The sums in order are 2, 3, 4, then 5. Two pairs sum to 5: (1, 4) at positions (0, 2) and (2, 3) at positions (1, 1). The one with the smaller i comes first, so [1, 4] is returned.

Example 2

Input: nums1 = [3, 3], nums2 = [3], k = 5

Output: [[3, 3], [3, 3]]

There are only two pairs, so both are returned.

Example 3

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

Output: [[-2, -1], [-2, 1], [0, -1]]

The sums are -3, -1, -1 and 1. The two pairs with sum -1 are ordered by i, so [-2, 1] comes before [0, -1].

Constraints