Find the -th smallest pairwise product formed by picking one element from each of two sorted arrays.
You are given two sorted integer arrays. Consider every possible product formed by choosing one number from the first array and one number from the second array.
Your task is to return the -th smallest value among all of these pairwise products.
Because the arrays are sorted, the number of possible products can be very large, so an efficient solution is required. Pay attention to negative numbers, zeros, and positive numbers, since they affect the ordering of products.
Input Format
- Two sorted integer arrays
nums1andnums2. - An integer
krepresenting the rank of the product to return.
Treat the arrays as already sorted in non-decreasing order.
Output Format
- Return a single integer: the -th smallest pairwise product among all values
nums1[i] * nums2[j].
Constraints
- Both arrays are sorted in non-decreasing order.
- The total number of pairwise products is
len(nums1) * len(nums2). 1 <= k <= len(nums1) * len(nums2).- Values may be negative, zero, or positive.
Exact official limits are not provided here; assume the input size is large enough that an enumeration is too slow.
Example 1
Input
nums1 = [1, 3, 5] nums2 = [2, 4, 6] k = 4
Output
12
Explanation
All pairwise products are [2, 4, 6, 6, 12, 18, 10, 20, 30]. Sorted: [2, 4, 6, 6, 10, 12, 18, 20, 30]. The 4th smallest is 6.
Example 2
Input
nums1 = [-4, -2, 0, 3] nums2 = [2, 4] k = 3
Output
0
Explanation
Pairwise products are [-8, -16, 0, 0, 6, 12, -4, -8]. Sorted: [-16, -8, -8, -4, 0, 0, 6, 12]. The 3rd smallest is -8.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.