We’re preparing your current view and syncing the latest data.
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Your task is to find k pairs (u, v) which consist of one element from the first array and one element from the second array such that their sums are the smallest. Return the list of pairs sorted in ascending order of their sums. If there are less than k valid pairs, return all possible pairs.
Two arrays nums1 and nums2, and an integer k.
An array of pairs [u, v] from nums1 and nums2 respectively.
1 <= nums1.length, nums2.length <= 10^5, -10^9 <= nums1[i], nums2[j] <= 10^9, 1 <= k <= 10^4
Example 1
Input
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output
[[1,2],[1,4],[1,6]]
Explanation
The first 3 pairs with the smallest sums are (1,2), (1,4), and (1,6).
Example 2
Input
nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output
[[1,1],[1,1]]
Explanation
The first 2 pairs with the smallest sums include the pairs (1,1) twice from the first two 1's in nums1.
Example 3
Input
nums1 = [1,2], nums2 = [3], k = 3
Output
[[1,3],[2,3]]
Explanation
There are only 2 possible pairs, both are returned.