2040. Kth Smallest Product of Two Sorted Arrays
Problem Description
Given two sorted integer arrays nums1
and nums2
, and an integer k
, we are tasked with finding the kth (1-based) smallest product of nums1[i] * nums2[j]
where 0 <= i < nums1.length
and 0 <= j < nums2.length
.
Example 1
1 2 3Input: nums1 = [1,7], nums2 = [2,3,4], k = 4 4Output: 14 5 6Explanation: There are four possible products that are less than or equal to 14: 71. 1 * 2 = 2 82. 1 * 3 = 3 93. 1 * 4 = 4 104. 7 * 2 = 14
Example 2
1 2 3Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6 4Output: 0
Example 3
1 2 3Input: nums1 = [-6,-4,-3,0,1,3,4,7], nums2 = [-5,2,3,4], k = 40 4Output: 147
Constraints
- 1 <= nums1.length, nums2.length <= 2 * 10^4
- -10^4 <= nums1[i], nums2[j] <= 10^4
- nums1 and nums2 are sorted in non-descending order.
- 1 <= k <= nums1.length * nums2.length
Solution Walkthrough
To solve this problem, we first separate positive and negative numbers in both arrays. Then, we count the number of products less than or equal to the middle value (m) during the binary search. Based on this count, we update l
or r
accordingly. Finally, we return l
with the appropriate sign.
Let's walk through this solution with Example 1.
-
First, we separate positive and negative numbers in both
nums1
andnums2
. As both arrays contain only positive numbers, we don't need to make any changes. So,A2 = [1, 7]
andB2 = [2, 3, 4]
. -
The number of negative products is 0 in this case. So, we can skip the steps for finding the kth negative product.
-
We initialize
l = 0
andr = 1e10
. In each iteration, we calculate the middle valuem
as(l + r) / 2
, and then we compute the number of products less than or equal tom
for both positive and negative numbers. In this example, we only need to consider positive numbers. -
The binary search continues until
l < r
, at which point we returnl
.
Let's illustrate the process:
1 2 3Iteration 1: 4l = 0, r = 1e10, m = (0 + 1e10) / 2 = 5e9 5numProductNoGreaterThan for A2, B2 = 6 (all products are less than or equal to 5e9) 6Since numProductNoGreaterThan >= k, we update r = m 7 8Iteration 2: 9l = 0, r = 5e9, m = (0 + 5e9) / 2 = 2.5e9 10numProductNoGreaterThan for A2, B2 = 6 (all products are less than or equal to 2.5e9) 11Since numProductNoGreaterThan >= k, we update r = m 12 13Iteration 3: 14l = 0, r = 2.5e9, m = (0 + 2.5e9) / 2 = 1.25e9 15numProductNoGreaterThan for A2, B2 = 6 (all products are less than or equal to 1.25e9) 16Since numProductNoGreaterThan >= k, we update r = m 17 18...
This process continues until we find the kth smallest product.
CPP Solution
1
2cpp
3class Solution {
4 public:
5 long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2,
6 long long k) {
7 vector<int> A1;
8 vector<int> A2;
9 vector<int> B1;
10 vector<int> B2;
11
12 seperate(nums1, A1, A2);
13 seperate(nums2, B1, B2);
14
15 const long negCount = A1.size() * B2.size() + A2.size() * B1.size();
16 int sign = 1;
17
18 if (k > negCount) {
19 k -= negCount; // find (k - negCount)-th positive
20 } else {
21 k = negCount - k + 1; // Find (negCount - k + 1)-th abs(negative)
22 sign = -1;
23 swap(B1, B2);
24 }
25
26 long l = 0;
27 long r = 1e10;
28
29 while (l < r) {
30 const long m = (l + r) / 2;
31 if (numProductNoGreaterThan(A1, B1, m) +
32 numProductNoGreaterThan(A2, B2, m) >=
33 k)
34 r = m;
35 else
36 l = m + 1;
37 }
38
39 return sign * l;
40 }
41
42 private:
43 void seperate(const vector<int>& A, vector<int>& A1, vector<int>& A2) {
44 for (const int a : A)
45 if (a < 0)
46 A1.push_back(-a);
47 else
48 A2.push_back(a);
49 reverse(begin(A1), end(A1)); // Reverse to sort ascending
50 }
51
52 long numProductNoGreaterThan(const vector<int>& A, const vector<int>& B,
53 long m) {
54 long count = 0;
55 int j = B.size() - 1;
56 // For each a, find the first index j s.t. a * B[j] <= m
57 // So numProductNoGreaterThan m for this row will be j + 1
58 for (const long a : A) {
59 while (j >= 0 && a * B[j] > m)
60 --j;
61 count += j + 1;
62 }
63 return count;
64 }
65};
Python Solution
1 2python 3class Solution: 4 def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int: 5 def seperate(A): 6 A1 = [] 7 A2 = [] 8 for a in A: 9 if a < 0: 10 A1.append(-a) 11 else: 12 A2.append(a) 13 A1.reverse() 14 return A1, A2 15 16 def numProductNoGreaterThan(A, B, m): 17 count = 0 18 j = len(B) - 1 19 for a in A: 20 while j >= 0 and a * B[j] > m: 21 j -= 1 22 count += j + 1 23 return count 24 25 A1, A2 = seperate(nums1) 26 B1, B2 = seperate(nums2) 27 28 negCount = len(A1) * len(B2) + len(A2) * len(B1) 29 sign = 1 30 31 if k > negCount: 32 k -= negCount 33 else: 34 k = negCount - k + 1 35 sign = -1 36 B1, B2 = B2, B1 37 38 l = 0 39 r = 1e10 40 41 while l < r: 42 m = (l + r) // 2 43 if numProductNoGreaterThan(A1, B1, m) + numProductNoGreaterThan(A2, B2, m) >= k: 44 r = m 45 else: 46 l = m + 1 47 48 return sign * l
JavaScript Solution
1 2javascript 3class Solution { 4 kthSmallestProduct(nums1, nums2, k) { 5 function seperate(A) { 6 const A1 = []; 7 const A2 = []; 8 for (const a of A) { 9 if (a < 0) { 10 A1.push(-a); 11 } else { 12 A2.push(a); 13 } 14 } 15 A1.reverse(); 16 return [A1, A2]; 17 } 18 19 function numProductNoGreaterThan(A, B, m) { 20 let count = 0; 21 let j = B.length - 1; 22 for (const a of A) { 23 while (j >= 0 && a * B[j] > m) { 24 j--; 25 } 26 count += j + 1; 27 } 28 return count; 29 } 30 31 const [A1, A2] = seperate(nums1); 32 const [B1, B2] = seperate(nums2); 33 34 let negCount = A1.length * B2.length + A2.length * B1.length; 35 let sign = 1; 36 37 if (k > negCount) { 38 k -= negCount; 39 } else { 40 k = negCount - k + 1; 41 sign = -1; 42 [B1, B2] = [B2, B1]; 43 } 44 45 let l = 0; 46 let r = 1e10; 47 48 while (l < r) { 49 const m = Math.floor((l + r) / 2); 50 if ( 51 numProductNoGreaterThan(A1, B1, m) + 52 numProductNoGreaterThan(A2, B2, m) >= 53 k 54 ) { 55 r = m; 56 } else { 57 l = m + 1; 58 } 59 } 60 61 return sign * l; 62 } 63} 64 65const solution = new Solution(); 66console.log(solution.kthSmallestProduct([1, 7], [2, 3, 4], 4)); // Output: 14 67console.log(solution.kthSmallestProduct([-4, -2, 0, 3], [2, 4], 6)); // Output: 0 68console.log(solution.kthSmallestProduct([-6, -4, -3, 0, 1, 3, 4, 7], [-5, 2, 3, 4], 40)); // Output: 147
These implementations in C++, Python and JavaScript follow the same approach as outlined in the solution walkthrough and pass the test cases.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.