Coding - Find K Pairs with Smallest Sums

Problem Statement

Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order, and an integer k. Return the k pairs (u, v) with the smallest sums, where u is from nums1 and v is from nums2.

Examples

Example 1: Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [1,2],[1,4],[1,6] Explanation: The smallest sums are 1+2=3, 1+4=5, 1+6=7.

Example 2: Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [1,1],[1,2] Explanation: The smallest sums are 1+1=2, 1+2=3.

Example 3: Input: nums1 = [1,2], nums2 = [3], k = 3 Output: [1,3],[2,3] Explanation: The smallest sums are 1+3=4, 2+3=5.

Constraints

• 1 <= nums1.length, nums2.length <= 105
• nums1.length == nums2.length
• -104 <= nums1[i], nums2[i] <= 104
• 1 <= k <= nums1.length
• nums1 and nums2 are sorted in non-decreasing order.

Hints

• Use a min-heap to keep track of the smallest sums.