0977HardArrayBinary Search

The k-th Smallest Product of Two Lists

Tracked in this browser only

Trains the technique from

LeetCode 2040Kth Smallest Product of Two Sorted Arrays

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two lists of readings are given as nums1 and nums2, each already in non-decreasing order. Either may hold negative readings.

Take every product of one reading from the first list with one from the second, keeping every combination of positions even when the products repeat. Return the k-th smallest of those products, counting from one.

Examples

Example 1

Input: nums1 = [-4, -2, 0, 3], nums2 = [-5, 1, 6], k = 7
Output: 0

The twelve products in order run -24, -12, -10, -6, -5, -2, 0, 0, 0, 3, 18 and 20, so the seventh is nothing.

Example 2

Input: nums1 = [-1], nums2 = [1], k = 1
Output: -1

The only product is a negative reading times a positive one.

Example 3

Input: nums1 = [2, 5], nums2 = [3, 4], k = 2
Output: 8

The four products are 6, 8, 15 and 20, so the second is 8.

Constraints

1 <= nums1.length <= 5 * 10^4
1 <= nums2.length <= 5 * 10^4
-10^5 <= nums1[i] <= 10^5
-10^5 <= nums2[i] <= 10^5
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are each in non-decreasing order

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def kth_smallest_product(nums1: list[int], nums2: list[int], k: int) -> int:

Java

public long kthSmallestProduct(int[] nums1, int[] nums2, long k)

The intended approach

Time O((n + m) log(V^2)) for lists of length n and m over readings up to V: one pass per candidate.Space O(1) beyond the input.

There are far too many products to list, so halve the range of possible product values instead and ask, for a candidate, how many products come out at most that. The answer is the smallest candidate for which that count reaches `k`. Counting the products at most a bound is one pass over the first list, using the second list's order. For a positive reading, the partner must be at most the bound divided by it, rounded down, and a search over the sorted second list counts those. For a negative reading the comparison turns round, so the partner must be at least the bound divided by it rounded up, and the count comes from the other end. A reading of nothing gives a product of nothing, so it contributes every partner when the bound allows nothing and none otherwise. Doing the divisions in whole numbers, rounding the right way for each sign, is what keeps the count exact.

Pythonentry point: kth_smallest_product

def kth_smallest_product(nums1, nums2, k):
    import bisect
    m = len(nums2)

    def at_most(bound):
        total = 0
        for a in nums1:
            if a == 0:
                if bound >= 0:
                    total += m
            elif a > 0:
                # partner must be at most bound / a, rounded down
                total += bisect.bisect_right(nums2, bound // a)
            else:
                # partner must be at least bound / a, rounded up
                need = -((-bound) // a)
                total += m - bisect.bisect_left(nums2, need)
        return total

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

The obvious version

Work out every product, sort them all, and read off the one wanted. Costs the two lists multiplied together, which is hopeless at the declared sizes but assumes nothing about order or sign.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_kth_smallest_product(nums1, nums2, k):
    products = []
    for a in nums1:
        for b in nums2:
            products.append(a * b)
    products.sort()
    return products[k - 1]

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in