Find K Pairs with Smallest Sums
Given two sorted arrays nums1 and nums2, find k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

30:00

Find K Pairs with Smallest Sums
medium
Topics
Companies

Given two sorted arrays nums1 and nums2, find 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]]
Constraints:

  • 1≤nums1.length,nums2.length≤1051 \leq \text{nums}_1.\text{length}, \text{nums}_2.\text{length} \leq 10^5

  • −109≤nums1[i],nums2[i]≤109-10^9 \leq \text{nums}_1[i], \text{nums}_2[i] \leq 10^9

  • Both nums1 and nums2 are sorted in non-decreasing order.

  • 1≤k≤1041 \leq k \leq 10^4

  • k≤nums1.length⋅nums2.lengthk \leq \text{nums}_1.\text{length} \cdot \text{nums}_2.\text{length}

Input
arr ={"nums1":[1,7,11],"nums2":[2,4,6],"k":3}

Initialize: nums1=[1,7,11], nums2=[2,4,6], k=3

nums1

1

7

11

0

1

2

nums2

2

4

6

0

1

2

Min Heap (sum, i, j)

3

(0, 0)

Result Pairs

Empty

Heap Size
1
Result Count
0
Variables
No variables to display
DepthFunction Call
Stack empty
0/16