Kth Smallest Product of Two Sorted Arrays

lcpy gen -n 2040   # by problem number
lcpy gen -s kth_smallest_product_of_two_sorted_arrays   # by problem name

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.

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.

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.

from bisect import bisect_left, bisect_right


class Solution:
    # Time: O((len(nums1) + len(nums2)) * log(len(nums2)) * log(max_product))
    # Space: O(1)
    def kth_smallest_product(self, nums1: list[int], nums2: list[int], k: int) -> int:
        def count_at_most(target: int) -> int:
            total = 0
            for a in nums1:
                if a == 0:
                    if target >= 0:
                        total += len(nums2)
                elif a > 0:
                    total += bisect_right(nums2, target // a)
                else:
                    total += len(nums2) - bisect_left(nums2, -(target // -a))
            return total

        low, high = -(10**10), 10**10
        while low < high:
            mid = (low + high) // 2
            if count_at_most(mid) >= k:
                high = mid
            else:
                low = mid + 1
        return low