hardHeap / Priority QueuePure DSA~35 min
K Pairs With the Smallest Sums From Two Sorted Arrays
Given two sorted arrays, find the k pairs (one element from each) with the smallest combined sums.
Problem
Given two sorted integer arrays nums1 and nums2 and an integer k, return the k pairs (u, v) with u from nums1 and v from nums2 that have the smallest sums u + v. Return any k smallest pairs.
Input
Two sorted arrays nums1 and nums2 and an integer k.
Output
A list of up to k pairs [u, v].
Constraints
- 1 <= nums1.length, nums2.length <= 10^5
- -10^9 <= values <= 10^9; both arrays sorted ascending
- 1 <= k <= 10^4
Examples
Example 1
Input
nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output
[[1,2],[1,4],[1,6]]
The three smallest sums all pair with 1.
Example 2
Input
nums1 = [1,2], nums2 = [3], k = 3
Output
[[1,3],[2,3]]
Only two pairs exist.