LeetCode Solutions Blog

Kth Smallest Product of Two Sorted Arrays

Number: 2150

Difficulty: Hard

Paid? No

Companies: LinkedIn

Problem Description

Given two sorted integer arrays nums1 and nums2 and an integer k, find the kth (1-indexed) smallest product formed by nums1[i] * nums2[j] for all valid indices i and j.

Key Insights

Both arrays are sorted but may contain negative, zero, and positive numbers.
The product space is not sorted in a simple way due to sign changes. Therefore, a brute-force approach (forming all products) is infeasible given the constraint sizes.
A binary search on the answer space (range of possible products) can be used. For a given candidate value, count the number of pairs whose product is less than or equal to that candidate.
Counting pairs correctly requires handling three cases (negative, zero, and positive) separately since multiplication with negatives reverses inequalities.

Space and Time Complexity

Time Complexity: O((n1 + n2) * log(max_value)), where max_value is the search range (~10^10) and n1, n2 are the lengths of the arrays. Space Complexity: O(1)

Solution

The solution uses binary search over the potential product values. We set the low and high bounds based on the minimum and maximum possible products computed from the extremes of both arrays. For a given candidate mid, we count how many pairs (i, j) have a product <= mid. Since nums1 and nums2 are sorted, we can efficiently count this by iterating over one array and using binary search (or two pointer technique) on appropriate partitions of the other array. Special care is taken to handle negative numbers, zeros, and positives in order to correctly determine the count of valid pairs. Based on the count, we adjust our binary search until we narrow down the kth smallest product.

Code Solutions

# Python solution with detailed comments
def kthSmallestProduct(nums1, nums2, k):
    # Helper function: count how many pairs have product <= x
    def count_pairs(x):
        count = 0
        n = len(nums2)
        
        # Count pairs for an element a in nums1 with appropriate binary search or two-pointer technique
        for a in nums1:
            # If a is zero, then product is 0.
            if a == 0:
                if x >= 0:
                    count += n
            elif a > 0:
                # For positive a, we want nums2[j] <= x // a
                # Use binary search for the rightmost index such that nums2[j] <= x // a.
                lo, hi = 0, n
                while lo < hi:
                    mid = (lo + hi) // 2
                    if a * nums2[mid] <= x:
                        lo = mid + 1
                    else:
                        hi = mid
                count += lo
            else:
                # a < 0. For negative a, inequality flips.
                # We want nums2[j] >= ceil(x / a). To count, we find the first index such that product <= x
                lo, hi = 0, n
                while lo < hi:
                    mid = (lo + hi) // 2
                    if a * nums2[mid] <= x:
                        hi = mid
                    else:
                        lo = mid + 1
                count += (n - lo)
        return count
    
    # Determine the search range. The minimum product is one of the extreme combinations.
    candidates = [nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1]]
    left, right = min(candidates), max(candidates)
    
    # Binary search for the kth smallest product.
    while left < right:
        mid = left + (right - left) // 2
        if count_pairs(mid) < k:
            left = mid + 1
        else:
            right = mid
    return left

# Example usage:
#print(kthSmallestProduct([2,5], [3,4], 2))  # Output: 8