Solution: Find K Pairs with Smallest Sums

Statement

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

Constraints:

• $1$ $\leq$ list1.length, list2.length $\leq$ $500$
• $-10^4$ $\leq$ list1[i], list2[i] $\leq$ $10^4$
• $1$ $\leq$ $k$ $\leq$ $10^3$
• Input lists should be sorted in ascending order.
• If the value of $k$ exceeds the total number of valid pairs that may be formed, return all the pairs.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

One way to solve this problem is by creating all possible pairs from the given lists. This creation of pairs costs $O(n_1 * n_2)$, where $n_1$ and $n_2$ are the lengths of two lists.

Note: Since we’re not certain whether or not the lengths of the two lists are the same, we’ll use $n_1$ ...