2040. Kth Smallest Product Of Two Sorted Arrays

Introduction

Finding the kth smallest product of two sorted arrays is a classic algorithmic challenge that appears frequently in coding interviews and competitive programming. When you have two arrays, A and B, each already sorted in non‑decreasing order, the task is to determine the k‑th smallest value among all possible products A[i] * B[j] (where 0 ≤ i < len(A) and 0 ≤ j < len(B)). Which means this problem tests your ability to combine sorting, binary search, and counting techniques to avoid the brute‑force O(mn) enumeration. In real terms, in this article we will explore the problem definition, discuss why a naive solution is impractical, and then develop an efficient O((m + n) log(maxProduct)) approach using binary search on the answer space. We also examine time‑ and space‑complexity, walk through a concrete example, and answer common questions that arise when solving this type of problem.

Quick note before moving on.

Problem Definition

Given two integer arrays A and B such that

• A is sorted in non‑decreasing order (A[0] ≤ A[1] ≤ … ≤ A[m‑1])
• B is sorted in non‑decreasing order (B[0] ≤ B[1] ≤ … ≤ B[n‑1])

and an integer k (1‑based), return the kth smallest product among the multiset

P = { A[i] * B[j] | 0 ≤ i < m, 0 ≤ j < n } .

Because both arrays are sorted, the products are not necessarily sorted, but there are structural properties we can exploit. The answer must be accurate even when duplicate products exist; the k‑th element counts duplicates as separate entries But it adds up..

Example

A = [1, 2, 3]
B = [4, 5, 6]
k = 5

All products (in sorted order) are:

1·4 = 4, 1·5 = 5, 1·6 = 6, 2·4 = 8, 2·5 = 10, 2·6 = 12, 3·4 = 12, 3·5 = 15, 3·6 = 18 It's one of those things that adds up..

The 5th smallest product is 10.

Naive Approaches

Brute‑Force Enumeration

The simplest method is to generate every product, sort the list, and pick the element at index k‑1. This requires O(mn) time to create the list and O(mn log(mn)) time to sort it, which is prohibitive for arrays larger than a few hundred elements Worth knowing..

Real talk — this step gets skipped all the time.

Two‑Pointer Scan (Only for Monotonic Cases)

If both arrays contain only non‑negative numbers, the product matrix is monotone: the smallest product is A[0] * B[0], and moving either pointer forward increases the product. In that special case a two‑pointer technique can find the kth smallest in O(k) time. On the flip side, when negative numbers are present, the monotonicity breaks down, and the two‑pointer method fails Simple, but easy to overlook..

Because real‑world inputs often include negatives, we need a solution that works for any integer values while preserving efficiency It's one of those things that adds up..

Efficient Algorithm: Binary Search on the Answer

The core insight is to treat the problem as a search on a numeric range. Worth adding: we can ask: *Is the kth smallest product ≤ X? * If we can answer this question quickly, we can binary‑search the smallest X that satisfies the condition.

Counting Products ≤ Mid

Given a candidate value mid, we need to count how many pairs (i, j) produce a product ≤ mid. Because both arrays are sorted, we can compute this count in O(m log n) (or O(n log m)) using the following logic:

1. Separate sign groups – Split each array into three segments: negative, zero, and positive numbers.
2. Handle zeros – Any product involving a zero equals zero, so if mid ≥ 0, add zeroCountA * totalB + zeroCountB * totalA - zeroCountA * zeroCountB (subtract double‑counted zero‑zero pairs).
3. Negative × Negative = Positive – For pairs where both numbers are negative, the product is positive. Since the arrays are sorted, the negatives appear at the beginning (or end) of each array. We can reverse the negative sub‑arrays to make them sorted increasingly (e.g., [-5, -3, -1] becomes [1, 3, 5] after absolute value) and then apply a two‑pointer count similar to the monotonic case.
4. Negative × Positive = Negative – Products are negative, so they are always ≤ any non‑negative mid. Count them directly: negA * posB + posA * negB.
5. Positive × Positive = Positive – Use a two‑pointer scan on the positive portions. For each a in posA, find the largest b in posB such that a * b ≤ mid. Because both are sorted increasingly, moving the pointer backwards yields O(m + n) total work.

Putting it together, the count function runs in O(m log n) (or O(n log m)) time, which is acceptable when we perform binary search over the product range Not complicated — just consistent. But it adds up..

Binary Search Bounds

The smallest possible product is min(A) * max(B) (if signs differ) or max(A) * max(B) when both are negative, while the largest possible product is max(A) * max(B) (if both positive) or min(A) * min(B) (if both negative). A safe universal bound is:

low  = min(A) * min(B)
high = max(A) * max(B)

If low > high, swap them (this occurs when one array is all negative and the other all positive). The binary search proceeds until low < high, narrowing the interval to the exact kth product That's the whole idea..

Algorithm Steps

1. Preprocess each array into three vectors: neg, zero, pos (keeping original order for negatives to allow reversal).
2. Define countLessOrEqual(x) using the steps above.
3. Initialize low = min(A) * min(B), high = max(A) * max(B).
4. While low < high:
   • mid = low + (high - low) // 2 (integer division, careful with negatives).
   • c = countLessOrEqual(mid).
   • If c < k, the answer is larger: low = mid + 1.
   • Else (c ≥ k), the answer is ≤ mid: high = mid.
5. Return low as the kth smallest product.

The algorithm works because countLessOrEqual is monotonic: as x increases, the count never decreases.

Complexity Analysis