[Leetcode] 2040. Kth Smallest Product of Two Sorted Arrays

https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays/description/?envType=daily-question&envId=2025-06-25

initial

kinda knew it was BS but even when we guess the actual answer, how do we count the number of products?

there are 3 main ways to count that
as we iter through nums1, we need to make sure n1*n2<=our guess value. Look at my comments i documented well.

Then the BS condition is if count(guess)>=k, we shift right closer to mid via right=mid. This is cuz we are looking for at least k products.

My original code used check(mid) ≤ k, which asks "are there at most k products ≤ mid?" But that's not what we want - we want "are there at least k products ≤ mid?"

sol

from bisect import bisect, bisect_left
from math import ceil 

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def check(guess):
            total = 0
            for n1 in nums1:
                if n1<0:
                    # n1*n2<=guess
                    # n2 >=guess/n1 (must flip the inequality cuz n1 is negative)
                    # bisect left cuz we ceil(guess/n1) so if ceil(3.5)=4, we get all the possible values smaller than 4 like all the multiple 3s
                    idx = bisect_left(nums2, ceil(guess/n1))
                    total += len(nums2)-idx
                if n1>0:
                    # n1*n2<=guess
                    # n2<=guess/n1
                    # bisect = bisect right
                    # use bisect cuz // floors the value so if 3.5 -> 3, we wanna get all the 3s and not bisect left when we meet the first 3 and disregard the rest of the 3s
                    idx = bisect(nums2, guess//n1)
                    total+=idx
                if n1==0 and guess>=0:
                    # 0*n2<=guess
                    # if guess is negative, theres no value of n2 that can satisfy the above equation so guess hast obe at least >=0
                    # in which case any value of n2 will fit in the formula
                    total+=len(nums2)
            return total

        left,right=-int(10e18),int(10e18)
        count = 0
        while left<right:
            mid = left+(right-left)//2
            if check(mid)>=k:
                right=mid
            else:
                left=mid+1
        return left

complexity

time and space

log n * n log n? cuz we are doing BS and inside the check function we iter through nums and do bisect which is log n? actually the BS time isnt log n but log range.

The total time complexity is (Number of binary search iterations) multiplied by (Time complexity of check function).
Total Time Complexity: O(log(Range) N log M)

If N and M are roughly the same size, say L = max(N, M), then it simplifies to:
O(log(Range) L log L)

space = n+m