2040. Kth Smallest Product of Two Sorted Arrays

The Kth Smallest Product of Two Sorted Arrays problem is a classic interview question that checks whether you can shift from generating pair products to searching the answer via counting. Many candidates try to enumerate and sort all n × m products or force a two-pointer merge because the arrays are sorted, but that becomes infeasible and often breaks once negatives and zeros enter the mix.

Problem statement

You’re given two sorted integer arrays, nums1 and nums2, and an integer k. Consider every possible pair (i, j) and the product nums1[i] * nums2[j]. Your task is to return the kth smallest product when all these products are ordered from smallest to largest (with k being 1-based).

The challenge is that there can be billions of pair products, and the presence of negative numbers and zeros means the ordering of products is not straightforward. A “generate and sort” approach becomes impossible, and even seemingly clever two-pointer ideas break because product order flips depending on signs.

Constraints:

• 1 ≤ nums1.length, nums2.length ≤ $5 * 10^4$
• $−10^5$ ≤ nums1[i], nums2[j] ≤ $10^5$
• 1 ≤ k ≤ nums1.length * nums2.length
• nums1 and nums2 are sorted.

Examples

Why generating every pair is impractical

There are len(nums1) * len(nums2) products. With lengths up to $5∗10^4$, the pair count can reach 2.5 billion, which is far beyond what you can enumerate, store, or sort. Even just iterating through all products would time out, and sorting them would be even worse.

The core issue is repeated work: most candidate products are irrelevant once you know roughly where the kth value must lie, but brute force computes them all anyway.

Optimized approach using Binary search

We can’t list every product from the two arrays because that would take too long. Instead, we guess a product value and ask: how many pairs of numbers (one from the first array, one from the second) produce a product that is at most this guess? If that count is at least k, then the real k-th smallest product must be at or below our guess, so we try a smaller guess. If the count is less than k, the k-th smallest product must be bigger, so we try a larger guess. This works because as our guess increases, the number of valid pairs can only stay the same or go up, never down.

The main trick is counting how many pairs are at most a given guess efficiently. Keep the second array sorted. Then handle the first array one number at a time: for a fixed number from the first array, you want to know how many numbers in the sorted second array keep the product at most the guess. Because the second array is sorted, the “good” numbers will always sit together at one end (either mostly on the left or mostly on the right), so you can find the cut point using binary search instead of scanning the whole array. Add up these counts across all numbers in the first array to get the total number of valid pairs.

Even with negative numbers, this per-element binary-search counting still works because the valid values in the sorted second array always form one continuous block.

Solution steps

• Initialize low = -10**10 and high = 10**10 as the minimum/maximum possible product values.
• Implement ceil_div(p, q) to compute ceil(p / q) correctly for negative divisors.
• Implement count_leq(v) to count how many products nums1[i] * nums2[j] are <= v:
  • For each x in nums1:
    • If x > 0, count how many y in nums2 satisfy y <= floor(v / x) using bisect_right.
    • If x < 0, count how many y in nums2 satisfy y >= ceil(v / x) using bisect_left.
    • If x == 0, add len(nums2) if v >= 0, otherwise add 0.
• Binary search while low < high:
  • Let mid = (low + high) // 2.
  • If count_leq(mid) >= k, move left by setting high = mid; otherwise set low = mid + 1.
• Return low.

Let’s look at the following illustration to get a better understanding of the solution.

1 / 6

Python implementation

Let’s look at the code for the solution we just discussed.

from bisect import bisect_left, bisect_right


def kthSmallestProduct(nums1, nums2, k):
    n2 = len(nums2)

    def ceil_div(p, q):
        """
        Ceiling division for integers, works even when q is negative.
        Python // is floor-division, so we implement ceil via:
            ceil(p/q) = -floor((-p)/q)
        """
        return -((-p) // q)

    def count_leq(v):
        """
        Count pairs (i, j) such that nums1[i] * nums2[j] <= v.
        nums2 is sorted.
        """
        total = 0
        for x in nums1:
            if x > 0:
                # Need y <= floor(v / x)
                t = v // x
                # bisect_right gives index after the last <= t => count of <= t
                total += bisect_right(nums2, t)

            elif x < 0:
                # Need y >= ceil(v / x) because dividing by negative flips inequality
                t = ceil_div(v, x)
                # elements >= t are from bisect_left(t) to end
                total += n2 - bisect_left(nums2, t)

            else:
                # x == 0 => product is 0 for all y
                if v >= 0:
                    total += n2

        return total

    # Binary search boundaries for the answer.
    # These bounds should cover all possible products given constraints.
    low, high = -10**10, 10**10

    # Standard lower-bound binary search for the smallest value "ans"
    # such that count_leq(ans) >= k.
    while low < high:
        mid = (low + high) // 2

        # If at least k products are <= mid, mid might be the answer (or too high)
        if count_leq(mid) >= k:
            high = mid
        else:
            # Otherwise, we need a larger value
            low = mid + 1

    return low
        
def main():

    nums1_list = [
        [2, 5],
        [-4, -2, 0, 3],
        [-2, -1, 0, 1, 2],
        [-5, -4, -2],
        [-100000, 100000],
    ]

    nums2_list = [
        [3, 4],
        [2, 4],
        [-3, -1, 2, 4, 5],
        [-3, -1],
        [-100000, 100000],
    ]

    k_list = [2, 6, 3, 1, 3]


    for i in range(len(k_list)):
        print("\tnums1:", nums1_list[i])
        print("\tnums2:", nums2_list[i])
        print("\tk:", k_list[i])
        result = kthSmallestProduct(nums1_list[i], nums2_list[i], k_list[i])
        print("\n\tResult:", result)
        print("-"*75)


if __name__ == "__main__":
    main()

Time complexity

Let m = len(nums1) and n = len(nums2). Each count query loops over nums1 and performs a binary search in nums2, which takes O(logn) time per element, so one counting pass is O(mlogn). The binary search over the answer range runs in a fixed number of iterations (about 60 at most for this integer range), so the total time is O(mlogn∗logR) where R is the product value range, and in practice it behaves like O(mlogn) times a small constant.

Space complexity

The algorithm uses O(1) extra space beyond the input arrays. It maintains a few integers and uses binary search operations without building any auxiliary pair lists.

Edge cases

• All zeros in one array
  Example: nums1 = [0, 0] , nums2 = [-5, 7] , k = 3
  Products are all 0, so the answer is 0. The solution counts n pairs for each 0 when x >= 0.
• Only negative values
  Example: nums1 = [-5, -1], nums2 = [-4, -2], k = 1
  Negative * negative becomes positive, and ordering can still be non-trivial. Counting via bounds remains correct because it never assumes product monotonicity globally.
• Mixed negatives, zeros, and positives
  Example: nums1 = [-1, 0, 2] , nums2 = [-3, 4], k = 2
  Multiple sign regimes coexist; per-a counting handles each case separately.
• Very large k near the end
  Example: k = len(nums1) * len(nums2)
  You’re effectively asking for the maximum product. The binary search still converges because count_leq(x) is monotone in x.

Common pitfalls

• Assuming products are “mergeable” because arrays are sorted
  Sorting inputs does not imply sorted pairwise products when negatives exist.
• Using integer division incorrectly for negatives
  For a < 0, you must use a correct ceil(x / a) bound; mixing floor and ceil will off-by-one the count and break the binary search.
• Off-by-one in k
k is 1-based, but the binary search logic naturally targets “smallest x with count >= k”, which matches 1-based ranking—don’t shift k.
• Trying to clamp search bounds too tightly without proof
  It’s tempting to use only endpoint products as min/max, but with negatives and zeros, safe bounds are easier and still efficient.