Loading problem…
You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k. Define a pair (u, v) which consists of one element from the first array and one element from the second array. Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.
Example 1
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: Pairing 1 with 2, 4 and 6 gives sums 3, 5 and 7. The next smallest pair, [7,2], sums to 9, so the three smallest are [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: Both 1s in nums1 pair with the 1 in nums2 for a sum of 2, the smallest possible. They count as two different pairs, so the answer is [1,1] twice.
Example 3
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: Only two pairs exist, [1,3] and [2,3], which is fewer than k = 3, so both are returned.
Because both arrays are sorted, the smallest sums form a frontier. Seed a min-heap with pairs (nums1[i], nums2[0]) for the first k rows. Each time you pop the smallest pair, push the next pair in that same row — this always exposes the next-smallest candidate.
Run checks all cases above. Submit evaluates all test cases.