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.

kthSmallestProduct.js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var kthSmallestProduct = function(nums1, nums2, k) {
    // The range for the possible product values.
    // the values in nums can be up to 10^5, so the product can be up to 10^10.
    let left = -1e10 - 7; // A sufficiently small number
    let right = 1e10 + 7; // A sufficiently large number
    let ans = 0;

    // We will binary search for the *value* of the k-th smallest product.
    while (left <= right) {
        // `mid` is our guess for the k-th smallest product.
        const mid = Math.floor((left + right) / 2);

        // We count how many products are less than or equal to our guess `mid`.
        const count = countLessOrEqual(nums1, nums2, mid);

        if (count >= k) {
            // If the count is at least k, then `mid` is a potential answer.
            // It's possible a smaller value also satisfies this, so we try the lower half.
            ans = mid;
            right = mid - 1;
        } else {
            // If the count is less than k, our guess `mid` is too small.
            // We must look for a larger product.
            left = mid + 1;
        }
    }

    return ans;
};

function countLessOrEqual(nums1, nums2, x) {
    let totalCount = 0;
    const n = nums2.length;

    // Iterate through each number in the first array.
    for (const num1 of nums1) {
        if (num1 > 0) {
            // Case 1: num1 is positive.
            // We need to find the count of `num2` such that `num1 * num2 <= x`,
            // which simplifies to `num2 <= x / num1`.
            // We can use binary search on `nums2` to find this count efficiently.
            let count = 0;
            let l = 0, r = n - 1;
            let boundary = -1; // Index of the rightmost element satisfying the condition
            while (l <= r) {
                const m = Math.floor((l + r) / 2);
                if (num1 * nums2[m] <= x) {
                    boundary = m;
                    l = m + 1; // Try to find a larger element in nums2
                } else {
                    r = m - 1;
                }
            }
            count = boundary + 1;
            totalCount += count;

        } else if (num1 < 0) {
            // Case 2: num1 is negative.
            // When we divide by a negative, the inequality flips.
            // We need `num2 >= x / num1`.
            // We use binary search to find the count of elements in nums2 that are
            // greater than or equal to `x / num1`.
            let count = 0;
            let l = 0, r = n - 1;
            let boundary = n; // Index of the leftmost element satisfying the condition
            while (l <= r) {
                const m = Math.floor((l + r) / 2);
                if (num1 * nums2[m] <= x) {
                    boundary = m;
                    r = m - 1; // Try to find an even smaller element in nums2
                } else {
                    l = m + 1;
                }
            }
            count = n - boundary;
            totalCount += count;
            
        } else { // num1 === 0
            // Case 3: num1 is zero.
            // The product is always 0.
            // If `x` is non-negative (0 or positive), then `0 <= x` is always true.
            // So, all `n` products with `num1=0` are valid.
            if (x >= 0) {
                totalCount += n;
            }
            // If x is negative, `0 <= x` is false, so we add 0.
        }
    }
    return totalCount;
}