Find K Pairs with Smallest Sums

Given two arrays and an integer k, find k pairs of numbers with the smallest sum so that in each pair, each array contributes one number to the pair.

K Pairs with Smallest Sums

Problem Statement

You are given two arrays and an integer k. Find k pairs of numbers that have the smallest sums. In each pair, one number comes from each array.

Constraints

• 1 ≤ list1.length, list2.length ≤ 500
• −10⁴ ≤ list1[i], list2[i] ≤ 10⁴
• 1 ≤ k ≤ 10³
• The input lists are already sorted in ascending order.
• If k is greater than the total number of possible pairs, return all the pairs.

Examples

Example 1

Input:

• list1 = [1, 7, 11]
• list2 = [2, 4, 6]
• k = 3

Explanation:

All possible pairs and their sums:

(1,2)=3, (1,4)=5, (1,6)=7, (7,2)=9, (7,4)=11, (7,6)=13, (11,2)=13, (11,4)=15, (11,6)=17

The 3 pairs with the smallest sums are (1,2), (1,4), and (1,6).

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

Example 2

Input:

• list1 = [1, 2]
• list2 = [3]
• k = 3

Explanation:

All possible pairs: (1,3) and (2,3) — only 2 valid pairs in total.

Since k = 3 is greater than the total number of valid pairs (2), we return all the pairs.

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

Example 3

Input:

• list1 = [1, 1, 2]
• list2 = [1, 2, 3]
• k = 2

Explanation:

The smallest sum pairs are: (1,1) = 2 (using the first 1 from list1), and another (1,1) = 2 (using the second 1 from list1).

The 2 pairs with the smallest sums are (1,1) and (1,1).

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

Solution

Since both lists are already sorted, we know that the smallest possible sums will always involve list2[0] (the smallest value in list2), paired with values from list1.

Steps

• We take the smaller of k and the length of list1. We pair each of these numbers from list1 with list2[0], and push all of these pairs into a min heap, ordered by their sum.
• Now, the pair with the smallest sum is always at the top of the heap. We repeat the following, until we've found k pairs or the heap is empty:
  • We pop the smallest pair from the heap and add it to our results.
  • Since we already used this pairing's index from list1, we now try to move forward in list2. We pair the same list1 value with the next element in list2 (if one exists), and push this new pair into the heap.
• This way, we always explore the next-smallest possible sum, without needing to generate every single pair upfront.

Code

function kSmallestPairs(list1, list2, k) {
    let listLength = list1.length;
    let minHeapForPairs = new MinHeap();
    let pairs = [];

    for (let i = 0; i < Math.min(k, listLength); i++) {
        minHeapForPairs.offer([list1[i] + list2[0], i, 0]);
    }

    let counter = 1;

    while (minHeapForPairs.size() > 0 && counter <= k) {
        let [sumOfPairs, i, j] = minHeapForPairs.poll();
        pairs.push([list1[i], list2[j]]);
        let nextElement = j + 1;

        if (list2.length > nextElement) {
            minHeapForPairs.offer([list1[i] + list2[nextElement], i, nextElement]);
        }
        counter++;
    }
    return pairs;
}