#2040

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Kth Smallest Product of Two Sorted Arrays

Find the kth smallest product from two sorted arrays using binary search across possible product values efficiently.

Problem Statement

Given two sorted arrays nums1 and nums2, find the kth smallest product of the form nums1[i] * nums2[j]. Each product is formed by multiplying one element from nums1 with one element from nums2. Both arrays may contain negative, zero, or positive numbers, and you must account for all combinations.

Return the kth smallest product after considering all possible pairs. Constraints: 1 <= nums1.length, nums2.length <= 5 * 10^4, -10^5 <= nums1[i], nums2[j] <= 10^5, 1 <= k <= nums1.length * nums2.length, and both arrays are sorted.

Examples

Example 1

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

Output: 8

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.

Example 2

Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6

Output: 0

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.

Example 3

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

Output: -6

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.

Constraints

1 <= nums1.length, nums2.length <= 5 * 104
-105 <= nums1[i], nums2[j] <= 105
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are sorted.

Solution Approach

Binary Search on Product Values

Apply binary search over the entire possible range of products from the arrays. At each step, pick a mid value and count how many products are less than or equal to it. Narrow the search interval until the kth smallest product is found.

Counting Products Efficiently

For each number in nums1, count how many numbers in nums2 produce a product <= mid. Handle negative numbers by reversing inequalities, zeros by including all zero products, and positives by direct counting. This avoids generating all products explicitly.

Sign-based Case Splitting

Split the problem into four cases: negative * negative, negative * positive, zero-involved products, and positive * positive. This ensures the count function respects the sorted order and correctly identifies the kth smallest product without errors.

Complexity Analysis

Metric	Value
Time	O((n_1 + n_2)\log C)
Space	O(1)

The time complexity is O((n1 + n2) * log C) where C is the range of possible products; each binary search step counts products in linear time. Space is O(1) as no extra storage is needed beyond indices and counters.

What Interviewers Usually Probe

Binary search over the valid product range indicates efficiency over brute force enumeration.
Handling negative and positive products separately tests problem decomposition skills.
Expect questions about counting pairs without generating all products.

Common Pitfalls or Variants

Common pitfalls

Forgetting to split counting logic for negative, zero, and positive numbers causes incorrect results.
Assuming all products are positive may miscount the kth smallest for mixed-sign arrays.
Not handling large input ranges efficiently can exceed time limits.

Follow-up variants

Finding the kth largest product instead of smallest requires reversing comparison logic.
Arrays not sorted require initial sorting, increasing time complexity to O(n log n) per array.
Finding kth smallest sum instead of product changes counting and case handling.

FAQ

What is the main approach to solve Kth Smallest Product of Two Sorted Arrays?

Use binary search over the possible product values and count how many pairs produce products less than or equal to the candidate value.

How do negative numbers affect the counting in this problem?

Negative numbers reverse the comparison direction when counting, so each case must be handled separately to maintain correct order.

Can this problem be solved with brute force?

Brute force requires generating all products, which is infeasible for large arrays; binary search on the answer space is necessary for efficiency.

Do zeros need special handling?

Yes, all zero products must be included in the count since they are neither negative nor positive, affecting the kth product position.

What pattern does GhostInterview emphasize for this problem?

Binary search over the valid answer space, splitting counting logic based on the signs of numbers to efficiently find the kth smallest product.

terminal

Solution

Solution 1: Binary Search

We can use binary search to enumerate the value of the product $p$, defining the binary search interval as $[l, r]$, where $l = -\textit{max}(|\textit{nums1}[0]|, |\textit{nums1}[n - 1]|) \times \textit{max}(|\textit{nums2}[0]|, |\textit{nums2}[n - 1]|)$, $r = -l$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count(p: int) -> int:
            cnt = 0
            n = len(nums2)
            for x in nums1:
                if x > 0:
                    cnt += bisect_right(nums2, p / x)
                elif x < 0:
                    cnt += n - bisect_left(nums2, p / x)
                else:
                    cnt += n * int(p >= 0)
            return cnt

        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))
        return bisect_left(range(-mx, mx + 1), k, key=count) - mx

Continue Practicing

#2035 partition array into two arrays to minimize sum difference #2054 two best non overlapping events #2055 plates between candles