You are given two integer arrays
arr1[]
and
arr2[]
sorted in ascending order and an integer
k
. Suppose a pair
(a, b)
which consists of one element from the first array and one element from the second array. Write a program to find the k pairs
(a1, b1)
,
(a2, b2)...(ak, bk)
with the smallest sums.
Example 1
Input: arr1[] = [2,8,12], arr2[] = [4,6,8], k = 3
Output: [[2,4],[2,6],[2,8]]
Explanation: The first 3 pairs are returned from the sequence: [2,4],[2,6],[2,8],[8,4],[8,6],[12,8],[8,8],[12,6],[12,8]
Example 2
Input: arr1[] = [3,3,4], arr2[] = [3,4,5], k = 2
Output: [3,3],[3,3]
Explanation: The first 2 pairs are returned from the sequence: [3,3],[3,3],[3,5],[4,3],[3,4],[4,4],[3,5],[3,5],[4,5]
Example 3
Input: arr1[] = [5,6], arr2[] = [7], k = 3
Output: [5,7],[6,7]
Explanation: All possible pairs are returned from the sequence: [5,7],[6,7]