nums1 and nums2 as well as an integer k, return the kth (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 = 2 Output: 8 Explanation: The 2 smallest products are: - nums1[0] * nums2[0] = 2 * 3 = 6 - nums1[0] * nums2[1] = 2 * 4 = 8 The 2nd smallest product is 8.
Example 2:
Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6 Output: 0 Explanation: The 6 smallest products are: - nums1[0] * nums2[1] = (-4) * 4 = -16 - nums1[0] * nums2[0] = (-4) * 2 = -8 - nums1[1] * nums2[1] = (-2) * 4 = -8 - nums1[1] * nums2[0] = (-2) * 2 = -4 - nums1[2] * nums2[0] = 0 * 2 = 0 - nums1[2] * nums2[1] = 0 * 4 = 0 The 6th smallest product is 0.
Example 3:
Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3 Output: -6 Explanation: The 3 smallest products are: - nums1[0] * nums2[4] = (-2) * 5 = -10 - nums1[0] * nums2[3] = (-2) * 4 = -8 - nums1[4] * nums2[0] = 2 * (-3) = -6 The 3rd smallest product is -6.
Constraints:
1 <= nums1.length, nums2.length <= 5 * 104-105 <= nums1[i], nums2[j] <= 1051 <= k <= nums1.length * nums2.lengthnums1 and nums2 are sorted.Problem Overview: You are given two sorted arrays and an integer k. The task is to find the kth smallest value among all possible products formed by multiplying one element from each array. The challenge comes from negative numbers, zeros, and large value ranges, which make naive enumeration impractical.
Approach 1: Using Min-Heap for Kth Smallest Product (O(k log n) time, O(n) space)
This method treats the multiplication pairs similarly to merging sorted lists. Because both arrays are sorted, the smallest products involving each element of nums1 can be pushed into a min-heap. Each heap entry stores the current product along with the indices used to generate it. When you pop the smallest product, push the next candidate product for that index pair. This approach iteratively extracts the next smallest product until the kth one appears. It works well when k is relatively small compared to n × m. The heap ensures each extraction costs O(log n) while preserving sorted order of candidate products.
Approach 2: Binary Search on Possible Products (O((n + m) log R) time, O(1) space)
The optimal solution searches the answer directly instead of generating products. Define a product range from the smallest possible multiplication to the largest. Perform binary search on this range and check how many pairs produce a value ≤ mid. Counting pairs efficiently relies on the arrays being sorted. For each element in the first array, determine how many elements in the second array produce products ≤ mid using pointer movement or binary search. Careful handling of negative numbers is required because the inequality direction flips when multiplying by negatives. This counting step runs in linear time across both arrays. If the count is at least k, move the search space left; otherwise move right. The final boundary gives the kth smallest product.
The binary search strategy leverages properties of sorted arrays and avoids generating all combinations. Instead of computing n × m products, it repeatedly counts how many fall within a threshold value.
Recommended for interviews: Interviewers typically expect the binary search on answer technique. The heap approach shows understanding of kth-element problems, but it struggles with very large product spaces. The binary search solution demonstrates stronger algorithmic reasoning and efficient use of sorted arrays with binary search counting.
The intuitive approach is to leverage a min-heap to track the smallest products as we iterate over the possible products. We can maintain a heap of size k to ensure that we can always access the kth smallest element efficiently after processing.
This approach involves iterating through each possible product, inserting it into a min-heap, and once the heap grows beyond size k, we pop the smallest element until we are left with a heap that contains exactly k elements, the largest of which is our kth smallest product.
In this Python solution, we use a min-heap to keep track of the smallest products. We iterate over each pair of numbers from nums1 and nums2, calculate the product, and push it into the heap. If the heap exceeds size k, the smallest element is popped, ensuring that the heap retains only the k smallest elements. The k-th smallest product is obtained by popping the heap.
Time Complexity: O(m * n * log(k)), where m and n are the lengths of nums1 and nums2 respectively.
Space Complexity: O(k) for the heap.
An advanced, optimized approach employs binary search to efficiently find the k-th smallest product. The idea is to leverage the sorted nature of the arrays and conduct binary search over the range of possible products.
Binary search is performed on the range from the smallest possible product (min(nums1)*min(nums2)) to the largest possible product (max(nums1)*max(nums2)). For each midpoint value, count the number of products which are less than or equal to this midpoint. Adjust the binary search bounds based on this count to isolate the k-th smallest product eventually.
In the Python version, we set up a binary search range between the minimum and maximum possible products. Using a helper function, count_less_equal, we count for each potential midpoint how many products are less than or equal to the midpoint. By determining whether this count meets 'k', we adjust our search range iteratively to home in on the k-th smallest product.
Time Complexity: O((m + n) * log(U)), where m and n are the lengths of the arrays and U is the product value range.
Space Complexity: O(1), as it uses constant space.
We can use binary search to enumerate the value of the product p, defining the binary search interval as [l, r], where l = -max(|nums1[0]|, |nums1[n - 1]|) times max(|nums2[0]|, |nums2[n - 1]|), r = -l.
For each p, we calculate the number of products less than or equal to p. If this number is greater than or equal to k, it means the k-th smallest product must be less than or equal to p, so we can reduce the right endpoint of the interval to p. Otherwise, we increase the left endpoint of the interval to p + 1.
The key to the problem is how to calculate the number of products less than or equal to p. We can enumerate each number x in nums1 and discuss in cases:
x > 0, then x times nums2[i] is monotonically increasing as i increases. We can use binary search to find the smallest i such that x times nums2[i] > p. Then, i is the number of products less than or equal to p, which is accumulated into the count cnt;x < 0, then x times nums2[i] is monotonically decreasing as i increases. We can use binary search to find the smallest i such that x times nums2[i] leq p. Then, n - i is the number of products less than or equal to p, which is accumulated into the count cnt;x = 0, then x times nums2[i] = 0. If p geq 0, then n is the number of products less than or equal to p, which is accumulated into the count cnt.This way, we can find the k-th smallest product through binary search.
The time complexity is O(m times log n times log M), where m and n are the lengths of nums1 and nums2, respectively, and M is the maximum absolute value in nums1 and nums2.
| Approach | Complexity |
|---|---|
| Using Min-Heap for Kth Smallest Product | Time Complexity: O(m * n * log(k)), where m and n are the lengths of nums1 and nums2 respectively. |
| Binary Search on Possible Products | Time Complexity: O((m + n) * log(U)), where m and n are the lengths of the arrays and U is the product value range. |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap for Kth Product | O(k log n) | O(n) | When k is small and you want a straightforward kth-element extraction approach |
| Binary Search on Product Range | O((n + m) log R) | O(1) | Best for large arrays or large k; avoids generating all pair products |
Kth Smallest Product of Two Sorted Arrays | Detailed Explanation | Leetcode 2040 | codestorywithMIK • codestorywithMIK • 12,624 views views
Watch 9 more video solutions →Practice Kth Smallest Product of Two Sorted Arrays with our built-in code editor and test cases.
Practice on FleetCode