2040. Kth Smallest Product of Two Sorted Arrays Hard

1/**
2 * [2040] Kth Smallest Product of Two Sorted Arrays
3 *
4 * 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.
5 *  
6 * Example 1:
7 * 
8 * Input: nums1 = [2,5], nums2 = [3,4], k = 2
9 * Output: 8
10 * Explanation: The 2 smallest products are:
11 * - nums1[0] * nums2[0] = 2 * 3 = 6
12 * - nums1[0] * nums2[1] = 2 * 4 = 8
13 * The 2^nd smallest product is 8.
14 * 
15 * Example 2:
16 * 
17 * Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
18 * Output: 0
19 * Explanation: The 6 smallest products are:
20 * - nums1[0] * nums2[1] = (-4) * 4 = -16
21 * - nums1[0] * nums2[0] = (-4) * 2 = -8
22 * - nums1[1] * nums2[1] = (-2) * 4 = -8
23 * - nums1[1] * nums2[0] = (-2) * 2 = -4
24 * - nums1[2] * nums2[0] = 0 * 2 = 0
25 * - nums1[2] * nums2[1] = 0 * 4 = 0
26 * The 6^th smallest product is 0.
27 * 
28 * Example 3:
29 * 
30 * Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
31 * Output: -6
32 * Explanation: The 3 smallest products are:
33 * - nums1[0] * nums2[4] = (-2) * 5 = -10
34 * - nums1[0] * nums2[3] = (-2) * 4 = -8
35 * - nums1[4] * nums2[0] = 2 * (-3) = -6
36 * The 3^rd smallest product is -6.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= nums1.length, nums2.length <= 5 * 10^4
42 * 	-10^5 <= nums1[i], nums2[j] <= 10^5
43 * 	1 <= k <= nums1.length * nums2.length
44 * 	nums1 and nums2 are sorted.
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays/
50// discuss: https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn kth_smallest_product(nums1: Vec<i32>, nums2: Vec<i32>, k: i64) -> i64 {
56        
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2040() {
68    }
69}
70