Find K Pairs with Smallest Sums
Return the k pairs with the smallest sums from two arrays.
Examples
Input: [[1,7,11],[2,4,6],3]
Output: [[1,2],[1,4],[1,6]]
Input: [[1,1,2],[1,2,3],2]
Output: [[1,1],[1,1]]
Hints
Initialize a min-heap with the first element of `nums1` paired with every element in `nums2`, storing tuples of `(sum, index_in_nums1, index_in_nums2)`.
After extracting the smallest sum from the heap, push the next candidate pair from `nums1` (i.e., increment the `nums1` index) if it exists, ensuring no duplicates are added.
Use a visited set to track processed pairs and avoid re-adding them to the heap, optimizing for cases where `nums1` or `nums2` contain duplicate values.
Related Problems
Find K Pairs with Smallest Sums
Return the k pairs with the smallest sums from two arrays.