Kth Smallest Product of Two Sorted Arrays - Video Solutions

Problem Overview: You are given two sorted arrays and an integer k. The task is to find the kth smallest value among all possible products formed by multiplying one element from each array. The challenge comes from negative numbers, zeros, and large value ranges, which make naive enumeration impractical.

Approach 1: Using Min-Heap for Kth Smallest Product (O(k log n) time, O(n) space)

This method treats the multiplication pairs similarly to merging sorted lists. Because both arrays are sorted, the smallest products involving each element of nums1 can be pushed into a min-heap. Each heap entry stores the current product along with the indices used to generate it. When you pop the smallest product, push the next candidate product for that index pair. This approach iteratively extracts the next smallest product until the kth one appears. It works well when k is relatively small compared to n × m. The heap ensures each extraction costs O(log n) while preserving sorted order of candidate products.

Approach 2: Binary Search on Possible Products (O((n + m) log R) time, O(1) space)

The optimal solution searches the answer directly instead of generating products. Define a product range from the smallest possible multiplication to the largest. Perform binary search on this range and check how many pairs produce a value ≤ mid. Counting pairs efficiently relies on the arrays being sorted. For each element in the first array, determine how many elements in the second array produce products ≤ mid using pointer movement or binary search. Careful handling of negative numbers is required because the inequality direction flips when multiplying by negatives. This counting step runs in linear time across both arrays. If the count is at least k, move the search space left; otherwise move right. The final boundary gives the kth smallest product.

The binary search strategy leverages properties of sorted arrays and avoids generating all combinations. Instead of computing n × m products, it repeatedly counts how many fall within a threshold value.

Recommended for interviews: Interviewers typically expect the binary search on answer technique. The heap approach shows understanding of kth-element problems, but it struggles with very large product spaces. The binary search solution demonstrates stronger algorithmic reasoning and efficient use of sorted arrays with binary search counting.