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.

1. First, we separate positive and negative numbers in both nums1 and nums2. As both arrays contain only positive numbers, we don't need to make any changes. So, A2 = [1, 7] and B2 = [2, 3, 4].

2. The number of negative products is 0 in this case. So, we can skip the steps for finding the kth negative product.

3. We initialize l = 0 and r = 1e10. In each iteration, we calculate the middle value m as (l + r) / 2, and then we compute the number of products less than or equal to m for both positive and negative numbers. In this example, we only need to consider positive numbers.

4. The binary search continues until l < r, at which point we return l.

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.

Solution Implementation