Kth Smallest Product Of Two Sorted Arrays - Leetcode Solution

The problem can be stated as follows: Given two sorted arrays of integers A and B and an integer K, find the Kth smallest product of any two integers, where the first integer is from A and the second integer is from B.

One way to solve this problem is to use binary search. We can first find the minimum and maximum possible products by multiplying the first and last elements of both arrays. Let minProd and maxProd be the minimum and maximum possible products, respectively. We can then perform binary search on the range [minProd, maxProd] to find the Kth smallest product.

In each iteration of binary search, we can count the number of products that are less than or equal to mid (the middle element of the range being searched). To count the number of products, we can start with the first element of A and the last element of B, and move towards the middle, checking the product of each pair of elements. If the product is less than or equal to mid, we can count it and move to the next element of A. If the product is greater than mid, we can move to the previous element of B.

If the number of products less than or equal to mid is less than K, we can increase mid and continue the binary search in the range [mid+1, maxProd]. If the number of products is greater than or equal to K, we can decrease mid and continue the binary search in the range [minProd, mid-1]. When the binary search terminates, the value of mid will be the Kth smallest product.

Here is the Python code that implements the algorithm:

def kthSmallestProduct(A, B, K): n, m = len(A), len(B) minProd, maxProd = A[0]*B[m-1], A[n-1]*B[0]

while minProd <= maxProd:
    mid = (minProd + maxProd) // 2

    count = 0
    j = m - 1
    for i in range(n):
        while j >= 0 and A[i]*B[j] > mid:
            j -= 1
        count += j + 1
    if count < K:
        minProd = mid + 1
    else:
        maxProd = mid - 1

return minProd

The time complexity of this algorithm is O(n log (maxProd - minProd)), where n is the length of A and m is the length of B. The space complexity is O(1).

1