Find K Pairs with Smallest Sums

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.

Examples

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy