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.
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
Solution Implementation
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Patterns The Shortest Path Algorithm for Coding Interviews The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we can determine the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster 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.