Kth Smallest Product of Two Sorted Arrays LeetCode Solution

Table of Contents

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

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

Notable issues:

typecast to long BEFORE min max
be aware of whether the binary search end is inclusive or not
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
      //products are 0, all products will be smaller or equal to midval. So we can add all products in the answer
      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)

Space Complexity

O(1)

Reference: https://en.wikipedia.org/wiki/Priority_queue