Solution: Find K Pairs with Smallest Sums

Let's solve the Find K Pairs with Smallest Sums problem using the K-Way Merge pattern.

Statement

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

Constraints:

  • 11 ≤\leq list1.length, list2.length ≤\leq 500500

  • −104-10^4 ≤\leq list1[i], list2[i] ≤\leq 10410^4

  • 11 ≤\leq kk ≤\leq 10310^3

  • Input lists should be sorted in ascending order.

  • If the value of kk exceeds the total number of valid pairs that may be formed, return all the pairs.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.