Kth Smallest Product of Two Sorted Arrays
Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the k^th (1-based) smallest product of nums1[i] * nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.
Example 1
Input
nums1 = [2,5], nums2 = [3,4], k = 2Output
8The two smallest products are 2 * 3 = 6 and 2 * 4 = 8, so the 2nd smallest product is 8.
Example 2
Input
nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6Output
0The six smallest products are -16, -8, -8, -4, 0, and 0, so the 6th smallest product is 0.
Constraints
- 1 <= nums1.length, nums2.length <= 5 * 10^4
- -10^5 <= nums1[i], nums2[j] <= 10^5
- 1 <= k <= nums1.length * nums2.length
- nums1 and nums2 are sorted.