Find K Pairs with Smallest Sums
Find K Pairs with Smallest Sums gives two sorted integer arrays and a number k. Return the k pairs, one value from each array, with the smallest possible sums.
We'll cover the following...
Statement
You are given two integer arrays, list1 and list2, sorted in non-decreasing order, and an integer, k.
A pair list1 and one element list2.
Your task is to return the k pairs
Note: If multiple pairs have the same sum, any order among them is acceptable.
Constraints:
-
list1.length,list2.length -
list1[i],list2[i] -
-
Input lists should be sorted in ascending order.
-
If the value of exceeds the total number of valid pairs that may be formed, return all the pairs.
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Find K Pairs with Smallest Sums
What is the output if the following lists and value of k is given as input?
list1 = [1, 11, 20, 35, 300]
list2 = [1, 2, 300]
k = 5
pairs = [[1, 1], [1, 2], [1, 300], [11, 1], [11, 2]]
pairs = [[1, 1], [1, 2], [11, 1], [11, 2], [11, 300]]
pairs = [[1, 1], [1, 2], [11, 1], [11, 2], [20, 2]]
pairs = [[1, 1], [1, 2], [11, 1], [11, 2], [20, 1]]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in main.go in the following coding playground. We have provided a useful code template in the other file that you may build on to solve this problem.
package mainfunc kSmallestPairs(list1 []int, list2 []int, k int) [][]int {result := make([][]int, 0)// Replace this placeholder return statement with your codereturn result}