2040. Kth Smallest Product of Two Sorted Arrays LeetCode Solution
In this guide, you will get 2040. Kth Smallest Product of Two Sorted Arrays LeetCode Solution with the best time and space complexity. The solution to Kth Smallest Product of Two Sorted Arrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Kth Smallest Product of Two Sorted Arrays
Given two sorted 0-indexed integer arrays 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.
1 <= nums1.length, nums2.length <= 5 * 104
-105 <= nums1[i], nums2[j] <= 105
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are sorted.
Complexity Analysis
Time Complexity: O(|\texttt{nums1}||\texttt{nums2}| \cdot \log 10^10)
Space Complexity: O(|\texttt{nums1}| + |\texttt{nums2}|)
2040. Kth Smallest Product of Two Sorted Arrays LeetCode Solution in C++
class Solution {
public:
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2,
long long k) {
vector<int> A1;
vector<int> A2;
vector<int> B1;
vector<int> B2;
seperate(nums1, A1, A2);
seperate(nums2, B1, B2);
const long negCount = A1.size() * B2.size() + A2.size() * B1.size();
int sign = 1;
if (k > negCount) {
k -= negCount; // Find the (k - negCount)-th positive.
} else {
k = negCount - k + 1; // Find the (negCount - k + 1)-th abs(negative).
sign = -1;
swap(B1, B2);
}
long l = 0;
long r = 1e10;
while (l < r) {
const long m = (l + r) / 2;
if (numProductNoGreaterThan(A1, B1, m) +
numProductNoGreaterThan(A2, B2, m) >=
k)
r = m;
else
l = m + 1;
}
return sign * l;
}
private:
void seperate(const vector<int>& arr, vector<int>& A1, vector<int>& A2) {
for (const int a : arr)
if (a < 0)
A1.push_back(-a);
else
A2.push_back(a);
ranges::reverse(A1); // Reverse to sort ascending
}
long numProductNoGreaterThan(const vector<int>& A, const vector<int>& B,
long m) {
long count = 0;
int j = B.size() - 1;
// For each a, find the first index j s.t. a * B[j] <= m
// So numProductNoGreaterThan m for this row will be j + 1
for (const long a : A) {
while (j >= 0 && a * B[j] > m)
--j;
count += j + 1;
}
return count;
}
}; /* code provided by PROGIEZ */
2040. Kth Smallest Product of Two Sorted Arrays LeetCode Solution in Java
class Solution {
public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
List<Integer> A1 = new ArrayList<>();
List<Integer> A2 = new ArrayList<>();
List<Integer> B1 = new ArrayList<>();
List<Integer> B2 = new ArrayList<>();
seperate(nums1, A1, A2);
seperate(nums2, B1, B2);
final long negCount = A1.size() * B2.size() + A2.size() * B1.size();
int sign = 1;
if (k > negCount) {
k -= negCount; // Find the (k - negCount)-th positive.
} else {
k = negCount - k + 1; // Find the (negCount - k + 1)-th abs(negative).
sign = -1;
List<Integer> temp = B1;
B1 = B2;
B2 = temp;
}
long l = 0;
long r = (long) 1e10;
while (l < r) {
final long m = (l + r) / 2;
if (numProductNoGreaterThan(A1, B1, m) + numProductNoGreaterThan(A2, B2, m) >= k)
r = m;
else
l = m + 1;
}
return sign * l;
}
private void seperate(int[] arr, List<Integer> A1, List<Integer> A2) {
for (final int a : arr)
if (a < 0)
A1.add(-a);
else
A2.add(a);
Collections.reverse(A1); // Reverse to sort ascending
}
private long numProductNoGreaterThan(List<Integer> A, List<Integer> B, long m) {
long count = 0;
int j = B.size() - 1;
// For each a, find the first index j s.t. a * B[j] <= m
// So numProductNoGreaterThan m for this row will be j + 1
for (final long a : A) {
while (j >= 0 && a * B.get(j) > m)
--j;
count += j + 1;
}
return count;
}
} // code provided by PROGIEZ
2040. Kth Smallest Product of Two Sorted Arrays LeetCode Solution in Python
class Solution:
def kthSmallestProduct(
self,
nums1: list[int],
nums2: list[int],
k: int,
) -> int:
A1 = [-num for num in nums1 if num < 0][::-1]
A2 = [num for num in nums1 if num >= 0]
B1 = [-num for num in nums2 if num < 0][::-1]
B2 = [num for num in nums2 if num >= 0]
negCount = len(A1) * len(B2) + len(A2) * len(B1)
if k > negCount: # Find the (k - negCount)-th positive.
k -= negCount
sign = 1
else:
k = negCount - k + 1 # Find the (negCount - k + 1)-th abs(negative).
sign = -1
B1, B2 = B2, B1
def numProductNoGreaterThan(A: list[int], B: list[int], m: int) -> int:
ans = 0
j = len(B) - 1
for i in range(len(A)):
# For each A[i], find the first index j s.t. A[i] * B[j] <= m
# So numProductNoGreaterThan m for this row will be j + 1
while j >= 0 and A[i] * B[j] > m:
j -= 1
ans += j + 1
return ans
l = 0
r = 10**10
while l < r:
m = (l + r) // 2
if (numProductNoGreaterThan(A1, B1, m) +
numProductNoGreaterThan(A2, B2, m) >= k):
r = m
else:
l = m + 1
return sign * l # code by PROGIEZ
