Description
Given two sorted arrays, find k pairs with the smallest sums. A pair consists of one element from each array. Return pairs in sorted order.
Examples
Input:
nums1 = [1,7,11], nums2 = [2,4,6], k = 3Output:
[[1,2],[1,4],[1,6]]Explanation:
3 smallest sum pairs.
Input:
nums1 = [1], nums2 = [1], k = 3Output:
[1]Explanation:
Edge case with a single-element array.
Input:
nums1 = [1,2,4,5,6], nums2 = [3,5,7,9], k = 5Output:
[[1,3],[2,3],[1,5],[4,3],[2,5]]Explanation:
Pairs ordered by sum: (1,3)=4, (2,3)=5, (1,5)=6, (4,3)=7, (2,5)=7. With k=5, we return the first 5 pairs. When sums are equal like (4,3) and (2,5) both equaling 7, either order is valid. A min-heap starting from (0,0) indices efficiently finds the k smallest pairs.
Constraints
- •
1 ≤ nums1.length, nums2.length ≤ 10⁵ - •
1 ≤ k ≤ 10⁴