2150. Kth Smallest Product Of Two Sorted Arrays¶

Difficulty: Hard

2150. Kth Smallest Product of Two Sorted Arrays

Hard

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.

<<<<

Example 1:

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 2^nd smallest product is 8.

Example 2:

Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0
Explanation: The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6^th smallest product is 0.

Example 3:

Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6
Explanation: The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3^rd smallest product is -6.

Constraints:

1 <= nums1.length, nums2.length <= 5 * 10⁴
-10⁵ <= nums1[i], nums2[j] <= 10⁵
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are sorted.

Solution¶

class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        int n = nums1.length, m = nums2.length;
        long low = -((long)(1e12)), high = (long)(1e12);
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (ok(nums1, nums2, mid, k))
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }
    private boolean ok(int arr[], int brr[], long req, long k) {
        int n = arr.length, m = brr.length;
        long count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                if (req >= 0)
                    count += m;
                continue;
            } else if (arr[i] < 0) {
                int low = 0, high = m - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (arr[i] * 1L * brr[mid] <= req)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                count += m - low;
            } else {
                int low = 0, high = m - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (arr[i] * 1L * brr[mid] <= req)
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
                count += low;
            }
        }
        return count < k;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here