2040. Kth Smallest Product of Two Sorted Arrays

Description

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.

 

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 2nd 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 6th 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 3rd smallest product is -6.

 

Constraints:

• 1 <= nums1.length, nums2.length <= 5 * 104
• -105 <= nums1[i], nums2[j] <= 105
• 1 <= k <= nums1.length * nums2.length
• nums1 and nums2 are sorted.

 

Solutions

Solution: Binary Search

• Time complexity: O((n+m)*log(maxProduct))
• Space complexity: O(n+m)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
const kthSmallestProduct = function (nums1, nums2, k) {
  const negNums1 = [];
  const posNums1 = [];
  let negNums2 = [];
  let posNums2 = [];

  for (const num of nums1) {
    num < 0 ? negNums1.push(-num) : posNums1.push(num);
  }

  for (const num of nums2) {
    num < 0 ? negNums2.push(-num) : posNums2.push(num);
  }

  const negCount = negNums1.length * posNums2.length + posNums1.length * negNums2.length;
  let sign = 1;
  let left = 0;
  let right = 10 ** 10;

  negNums1.reverse();
  negNums2.reverse();

  if (k > negCount) {
    k -= negCount;
  } else {
    sign = -1;
    k = negCount - k + 1;
    [negNums2, posNums2] = [posNums2, negNums2];
  }

  const getSmallerCount = (a, b, product) => {
    let count = 0;
    let index = b.length - 1;

    for (const num of a) {
      while (index >= 0 && num * b[index] > product) {
        index -= 1;
      }

      count += index + 1;
    }

    return count;
  };

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const kth = getSmallerCount(negNums1, negNums2, mid) + getSmallerCount(posNums1, posNums2, mid);

    kth >= k ? (right = mid) : (left = mid + 1);
  }

  return left * sign;
};