2040. Kth Smallest Product of Two Sorted Arrays

[mah-shamim]

Topics: Array, Binary Search

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 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 * 104
• -105 <= nums1[i], nums2[j] <= 105
• 1 <= k <= nums1.length * nums2.length
• nums1 and nums2 are sorted.

Hint:

1. Can we split this problem into four cases depending on the sign of the numbers?
2. Can we binary search the value?

[mah-shamim]

We need to find the k-th smallest product of pairs from two sorted arrays. The challenge lies in efficiently handling both negative and non-negative numbers while leveraging the sorted nature of the arrays to avoid a brute-force approach.

Approach

1. Separate Arrays by Sign:

   • Split each array into two parts: one containing the absolute values of negative numbers (sorted in ascending order) and another containing non-negative numbers (including zeros).

2. Count Negative Products:

   • Calculate the total number of strictly negative products. This is derived from combinations of negative numbers from one array and non-negative numbers from the other array.

3. Determine Sign and Adjust k:

   • If k exceeds the count of negative products, the k-th smallest product is non-negative. Adjust k by subtracting the count of negative products.
   • Otherwise, the k-th smallest product is negative. Adjust k to find the corresponding absolute value among negative products and swap the non-negative and negative parts of the second array to simplify counting.

4. Binary Search for k-th Product:

   • Use binary search on the possible product values (from 0 to 10¹⁰) to find the smallest value m such that the count of products (absolute values for negative products) less than or equal to m is at least k.
   • For each candidate m during binary search, count the number of valid products in both parts of the separated arrays using a two-pointer technique for efficiency.

5. Return Result:

   • Multiply the found product value by the determined sign (1 for non-negative, -1 for negative) to get the k-th smallest product.

Let's implement this solution in PHP: 2040. Kth Smallest Product of Two Sorted Arrays

<?php
/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @param Integer $k
 * @return Integer
 */
function kthSmallestProduct($nums1, $nums2, $k) {
    $A1 = []; $A2 = [];
    $B1 = []; $B2 = [];

    separate($nums1, $A1, $A2);
    separate($nums2, $B1, $B2);

    $negCount = count($A1) * count($B2) + count($A2) * count($B1);
    $sign = 1;

    if ($k > $negCount) {
        $k -= $negCount;
    } else {
        $k = $negCount - $k + 1;
        $sign = -1;
        list($B1, $B2) = [$B2, $B1];
    }

    $left = 0;
    $right = 10000000000;

    while ($left < $right) {
        $mid = intval(($left + $right) / 2);
        $count1 = numProductNoGreaterThan($A1, $B1, $mid);
        $count2 = numProductNoGreaterThan($A2, $B2, $mid);
        $total = $count1 + $count2;
        if ($total >= $k) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }

    return $sign * $left;
}

/**
 * @param $arr
 * @param $neg
 * @param $nonNeg
 * @return void
 */
function separate($arr, &$neg, &$nonNeg) {
    foreach ($arr as $num) {
        if ($num < 0) {
            $neg[] = -$num;
        } else {
            $nonNeg[] = $num;
        }
    }
    $neg = array_reverse($neg);
}

/**
 * @param $A
 * @param $B
 * @param $m
 * @return int
 */
function numProductNoGreaterThan($A, $B, $m) {
    if (empty($A) || empty($B)) {
        return 0;
    }
    $count = 0;
    $j = count($B) - 1;
    foreach ($A as $a) {
        while ($j >= 0 && $a * $B[$j] > $m) {
            $j--;
        }
        $count += $j + 1;
    }
    return $count;
}

// Test cases
echo kthSmallestProduct([2, 5], [3, 4], 2) . "\n"; // Output: 8
echo kthSmallestProduct([-4, -2, 0, 3], [2, 4], 6) . "\n"; // Output: 0
echo kthSmallestProduct([-2, -1, 0, 1, 2], [-3, -1, 2, 4, 5], 3) . "\n"; // Output: -6
?>

Explanation:

1. Separation by Sign: The arrays nums1 and nums2 are split into negative and non-negative parts. Negative numbers are stored as their absolute values and reversed to ensure ascending order.
2. Negative Product Count: The total number of strictly negative products is computed by considering combinations of negative numbers from one array with non-negative numbers from the other.
3. Adjust k Based on Sign: If k is within the range of negative products, we adjust k to find the corresponding absolute value among negative products and swap parts of the second array. Otherwise, we proceed to find the k-th non-negative product.
4. Binary Search: The binary search is performed over possible product values (0 to 10¹⁰). For each midpoint m, we count how many products (from both parts of the separated arrays) are less than or equal to m using an efficient two-pointer approach.
5. Result Calculation: The result is derived by multiplying the smallest valid product found during binary search by the determined sign (1 or -1), ensuring the correct k-th smallest product is returned.

This approach efficiently narrows down the search space using binary search and leverages the sorted nature of arrays to count valid products in linear time, making it suitable for large input sizes.

[kovatz]

Thanks for solving the problem of "Kth Smallest Product of Two Sorted Arrays"

[mah-shamim]

Thanks