Formatted question description: https://leetcode.ca/all/2040.html

2040. Kth Smallest Product of Two Sorted Arrays

  • Difficulty: Hard.
  • Related Topics: Array, Binary Search.
  • Similar Questions: Find K Pairs with Smallest Sums, K-diff Pairs in an Array.

Problem

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.

Solution

  • class Solution {
        static long inf = (long) 1e10;
    
        public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
            int n = nums2.length;
            long lo = -inf - 1;
            long hi = inf + 1;
            while (lo < hi) {
                long mid = lo + ((hi - lo) >> 1);
                long cnt = 0;
                for (int i : nums1) {
                    int l = 0;
                    int r = n - 1;
                    int p = 0;
                    if (0 <= i) {
                        while (l <= r) {
                            int c = l + ((r - l) >> 1);
                            long mul = i * (long) nums2[c];
                            if (mul <= mid) {
                                p = c + 1;
                                l = c + 1;
                            } else {
                                r = c - 1;
                            }
                        }
                    } else {
                        while (l <= r) {
                            int c = l + ((r - l) >> 1);
                            long mul = i * (long) nums2[c];
                            if (mul <= mid) {
                                p = n - c;
                                r = c - 1;
                            } else {
                                l = c + 1;
                            }
                        }
                    }
                    cnt += p;
                }
                if (cnt >= k) {
                    hi = mid;
                } else {
                    lo = mid + 1L;
                }
            }
            return lo;
        }
    }
    
  • Todo
    
  • # 2040. Kth Smallest Product of Two Sorted Arrays
    # https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays
    
    class Solution:
        def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
            A1, A2 = [-x for x in nums1 if x < 0][::-1], [x for x in nums1 if x >= 0]
            B1, B2 = [-x for x in nums2 if x < 0][::-1], [x for x in nums2 if x >= 0]
            
            neg = len(A1) * len(B2) + len(A2) * len(B1)
            if k > neg:
                k -= neg
                s = 1
            else:
                k = neg - k + 1
                B1, B2 = B2, B1
                s = -1
            
            def count(A, B, t):
                res = 0
                
                j = len(B) - 1
                for x in A:
                    while j >= 0 and x * B[j] > t:
                        j -= 1
                    
                    res += j + 1
                
                return res
            
            left, right = 0, 10 ** 10
            
            while left < right:
                mid = left + (right - left) // 2
                
                if count(A1, B1, mid) + count(A2, B2, mid) >= k:
                    right = mid
                else:
                    left = mid + 1
            
            return left * s
    
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions