# Kth Smallest Product of Two Sorted Arrays LeetCode Solution

Difficulty Level Hard

## Problem Statement

Kth Smallest Product of Two Sorted Arrays LeetCode Solution – Given two sorted 0-indexed integer arrays `nums1` and `nums2` as well as an integer `k`, return the `k`th (1-based) smallest product of `nums1[i] * nums2[j]` where `0 <= i < nums1.length` and `0 <= j < nums2.length`.

```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.
```

## Explanation

#### Intuition

• I can put the index pair for the two arrays in a priority queue and compute the answer gradually. However, the K can be up to 10^9. This will lead to TLE.
• The element can be negative. Maybe I need to know the number of negative elements and handle 4 different combinations: (negative array 1, negative array 2), (negative array 1, positive array 2), (positive array 1, negative array 2), (positive array 1, positive array 2). At least, I can know the number of products of each combination and locate k-th product among them.
• Even though I know which combination the k-th product belongs to, it doesn’t guarantee I can use the priority queue approach. I need another hint.
• Continuing with the above, I think I need some way to eliminate a number of products step by step to reach the goal.
• Since the array is sorted, if I turn my attention on nums1[i] x nums2[j], I can know there are j + 1 products which are less than or equal to nums1[i] x nums2[j] that are generated by nums1[i]. Then I realize that I should try the binary search.

Algorithm

• For each nums1[i], count the number of products that are less than or equal to the current guess

Notable issues:

1. typecast to long BEFORE min max
2. be aware of whether the binary search end is inclusive or not
3. be aware the count/index update is happening in which if clause to confirm it is the largest value have k count less than it or

## Code

### C++ Code for Kth Smallest Product of Two Sorted Arrays

```class Solution {
public:
bool check(long long midval,vector<int>& nums1, vector<int>& nums2, long long k){
long long cnt=0;
for(int i=0;i<nums1.size();i++)
{
long long val=nums1[i];

//If val == 0, product of val and each element in nums2 will be 0. And if midval>=0, then because all
if(val==0 and midval>=0)
cnt+=nums2.size();

else if(val>0)
cnt+=findmaxIndex(nums2,val,midval);

else if(val<0)
cnt+=findminIndex(nums2,val,midval);
}
return cnt>=k;
}

int findmaxIndex(vector<int>&nums2 , long long  val , long long midval)
{
int l = 0  , r = nums2.size()-1 , res=  -1;
while(l<=r)
{
long long mid = (l+r)/2;
if(val*nums2[mid]<=midval)
{
res=mid;
l=mid+1;
}
else r=mid-1;
}
return res+1;
}

int findminIndex(vector<int>&nums2 , long long  val , long long midval)
{
int l = 0  , r = nums2.size()-1 , res=  r+1;
while(l<=r)
{
long long mid = (l+r)/2;
if(val*nums2[mid]<=midval)
{
res=mid;
r=mid-1;
}
else l=mid+1;
}
return nums2.size()-res;
}

long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
long long l=-1e10,r=1e10,res=-1;
while(l<=r){
long long mid = (l+r)/2;
// cout<<mid<<endl;
if(check(mid,nums1,nums2,k)) {
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
};```

### Java Code for Kth Smallest Product of Two Sorted Arrays

```class Solution {
static long INF = (long) 1e10;
public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
int m = nums1.length, n = nums2.length;
long lo = -INF - 1, hi = INF + 1;
while (lo < hi) {
long mid = lo + ((hi - lo) >> 1), cnt = 0;
for (int i : nums1) {
if (0 <= i) {
int l = 0, r = n - 1, p = 0;
while (l <= r) {
int c = l + ((r - l) >> 1);
long mul = i * (long) nums2[c];
if (mul <= mid) {
p = c + 1;
l = c + 1;
} else r = c - 1;
}
cnt += p;
} else {
int l = 0, r = n - 1, p = 0;
while (l <= r) {
int c = l + ((r - l) >> 1);
long mul = i * (long) nums2[c];
if (mul <= mid) {
p = n - c;
r = c - 1;
} else l = c + 1;
}
cnt += p;
}
}
if (cnt >= k) {
hi = mid;
} else lo = mid + 1L;
}
return lo;
}
}```

## Complexity Analysis for Kth Smallest Product of Two Sorted Arrays LeetCode Solution

### Time Complexity

O (10^10 x M log N)

O(1)

Translate »