Solution: Find K Pairs with Smallest Sums

Statement

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.

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 arrays. This creation of pairs costs $O(n_1 * n_2)$, where $n_1$ and $n_2$ are the lengths of two arrays.

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