2040. Kth Smallest Product of Two Sorted Arrays - Explanation

Description

You are 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 <= 50,000
-100,000 <= nums1[i], nums2[j] <= 100,000
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are sorted.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        prod = []

        for i in range(len(nums1)):
            for j in range(len(nums2)):
                prod.append(nums1[i] * nums2[j])

        prod.sort()
        return prod[k - 1]

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ , respectively.

2. Binary Search

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count(prod):
            cnt = 0
            n2 = len(nums2)
            for a in nums1:
                if a > 0:
                    cnt += bisect.bisect_right(nums2, prod // a)
                elif a < 0:
                    threshold = math.ceil(prod / a)
                    idx = bisect.bisect_left(nums2, threshold)
                    cnt += n2 - idx
                else:
                    if prod >= 0:
                        cnt += n2
            return cnt


        l, r = -(10**10), 10**10
        while l <= r:
            m = l + (r - l) // 2
            if count(m) < k:
                l = m + 1
            else:
                r = m - 1
        return l

Time & Space Complexity

Time complexity: $O(m \log (\log N))$
Space complexity: $O(1)$

Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ , respectively. $N$ is the size of the range of the product.

3. Binary Search + Two Pointers

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        n1, n2 = len(nums1), len(nums2)
        pos1 = 0 # first non-negative in nums1
        while pos1 < n1 and nums1[pos1] < 0:
            pos1 += 1

        pos2 = 0 # first non-negative in nums2
        while pos2 < n2 and nums2[pos2] < 0:
            pos2 += 1

        def count(prod):
            cnt = 0

            # negative * negative -> positive
            i, j = 0, pos2 - 1
            while i < pos1 and j >= 0:
                if nums1[i] * nums2[j] > prod:
                    i += 1
                else:
                    cnt += (pos1 - i)
                    j -= 1

            # positive * positive -> positive
            i, j = pos1, n2 - 1
            while i < n1 and j >= pos2:
                if nums1[i] * nums2[j] > prod:
                    j -= 1
                else:
                    cnt += (j - pos2 + 1)
                    i += 1

            # negative * positive -> negative
            i, j = 0, pos2
            while i < pos1 and j < n2:
                if nums1[i] * nums2[j] > prod:
                    j += 1
                else:
                    cnt += (n2 - j)
                    i += 1

            # positive * negative → negative
            i, j = pos1, 0
            while i < n1 and j < pos2:
                if nums1[i] * nums2[j] > prod:
                    i += 1
                else:
                    cnt += (n1 - i)
                    j += 1

            return cnt

        left, right = -10**10, 10**10
        while left <= right:
            mid = (left + right) // 2
            if count(mid) < k:
                left = mid + 1
            else:
                right = mid - 1

        return left

Time & Space Complexity

Time complexity: $O((m + n) \log N)$
Space complexity: $O(1)$

Where $m$ and $n$ are the lengths of the arrays $nums1$ and $nums2$ , respectively. $N$ is the size of the range of the product.