Return the pairs formed from two sorted arrays that have the smallest sums.
Problem
You are given two integer arrays nums1 and nums2, each sorted in non-decreasing order, and an integer k.
Form pairs (u, v) where u comes from nums1 and v comes from nums2. Your task is to return the k pairs with the smallest sums u + v.
If fewer than k pairs exist, return all of them.
Notes
- A pair is represented as
[u, v]. - If multiple pairs have the same sum, any valid order is acceptable unless otherwise stated.
- The arrays are already sorted, which is an important part of the problem.
Input Format
Input
nums1: a sorted integer arraynums2: a sorted integer arrayk: an integer
Output Format
Output
- Return a list of up to
kpairs[u, v]with the smallest sums.
Constraints
1 <= nums1.length, nums2.lengthk >= 1- Arrays are sorted in non-decreasing order
- If
kexceeds the total number of possible pairs, return all pairs
Example 1
Input
nums1 = [1, 7, 11] nums2 = [2, 4, 6] k = 3
Output
[[1,2],[1,4],[1,6]]
Explanation
The three smallest pair sums are 3, 5, and 7, produced by pairs [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 smallest sums are both 2, coming from the two distinct pairs that use the first two 1s from nums1 with 1 from nums2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.