Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Counting how many products are at most a candidate value is easier than listing every product. That count is nondecreasing, so the kth product is the smallest value whose count reaches k. Negative factors reverse the inequality and require different binary-search boundaries.

Approach

For a candidate t, iterate values a from the first array. If a > 0, count second-array values at most floor(t/a). If a < 0, count values at least ceil(t/a). For zero, count the entire second array only when t >= 0. Use binary searches on the sorted second array for these counts. Binary-search the allowed product range, keeping the lower boundary of values with count at least k. Duplicate products count separately by index pair, and the sign-aware rounding preserves the inclusive comparison.

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

        def products(target):
            count = 0
            for n1 in nums1:
                if n1 > 0: count += bisect_right(nums2, target // n1)
                elif n1 < 0: count += m - bisect_left(nums2, ceil(target / n1))
                elif n1 == 0 and target >= 0: count += m
            return count
        
        l, r = -10**5 * 10**5, 10**5 * 10**5

        while l < r:
            mid = l + (r - l) // 2
            if products(mid) >= k:  r = mid
            else: l = mid + 1
        
        return l

Complexity analysis

Let n = nums1.length, m = nums2.length and V be the number of integer values in the searched range [-10^10, 10^10]. Each outer binary-search step scans all n values and performs at most one O(log(m + 1)) bound search per value. Time is O(n log(m + 1) log V), including the linear scan when m = 1; auxiliary space is O(1). Products and pair counts fit exactly in JavaScript Number under the stated constraints. For the displayed floor/ceil divisions, the bounded numerator and divisor also keep a nonintegral quotient safely away from an integer-rounding boundary.