Problem Description
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.
Key Insights
- The products of two sorted arrays can be efficiently determined using binary search.
- The range of possible product values can be established based on the extreme values of the elements in the arrays.
- By counting how many products are less than or equal to a mid value, we can narrow down the value of k-th smallest product.
Space and Time Complexity
Time Complexity: O(log(max_product) * (m + n)), where m is the length of nums1 and n is the length of nums2.
Space Complexity: O(1).
Solution
The approach involves using binary search on the product values. We define the search space from the minimum possible product (the smallest value of nums1 multiplied by the smallest value of nums2) to the maximum possible product (the largest value of nums1 multiplied by the largest value of nums2). In each iteration of the binary search, we calculate the mid product and count how many products are less than or equal to this mid value by iterating through one of the arrays and utilizing binary search on the other array. Based on the count, we adjust our search range until we find the k-th smallest product.