Problem statement

https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays/

Solution

The idea of this problem is to use binary search: let check(x) be the answer to the question: how many products are less or equal than x. Then we use binary search and find the first moment where we have exactly k such numbers.

  1. If n1 is positive, then values in nums2 * n1 go in increasing order, so we use bisect to find number of values which are <= x//n1.
  2. If n1 is negative, then values in nums2 * n1 going in decreasing order, so we need to take the right part.
  3. If n1 equal to 0, than all values in nums2 * n1 are equal to 0. So, we update total only if x >= 0.

Complexity

Time complexity is O(n*log m* log N), where n = len(nums1), m = len(nums2) and N = 10**10 + 10 is the maximum value of product. Space complexity is O(1)

Code

from bisect import bisect, bisect_left

class Solution:
    def kthSmallestProduct(self, nums1, nums2, k):
        def check(x):
            total = 0
            for n1 in nums1:
                if n1 > 0: total += bisect(nums2, x//n1)
                if n1 < 0: total += len(nums2) - bisect_left(nums2, ceil(x/n1))
                if n1 == 0 and x >= 0: total += len(nums2)

            return total

        beg, end = -10**10 - 1, 10**10 + 1

        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid) >= k:
                end = mid
            else:
                beg = mid

        return beg + 1