Kth Smallest Product of Two Sorted Arrays
Hard · Binary Search · Explanation and code example
Binary Search + Two Pointers
How it works
We can optimize the counting step using two pointers instead of binary search for each element. By separating negative and non-negative numbers in both arrays, we handle four cases: negative times negative (positive result), positive times positive, negative times positive, and positive times negative. For each case, two pointers can efficiently count products less than or equal to the target by exploiting monotonicity.
Steps
- Find the boundary indices where negative numbers end in both arrays (
pos1,pos2). - Binary search on the product value.
- For each candidate, count products using four two-pointer traversals:
- Negatives from
nums1with negatives fromnums2(yields positives). - Positives from
nums1with positives fromnums2. - Negatives from
nums1with positives fromnums2(yields negatives). - Positives from
nums1with negatives fromnums2.
- Negatives from
- Adjust pointers based on whether the current product exceeds the target.
- Return the smallest product where count >=
k.
Complexity
- Time complexity:
O((m + n) log N) - Space complexity:
O(1)
Where
mandnare the lengths of the arraysnums1andnums2, respectively.Nis the size of the range of the product.
Things to watch for
Integer Overflow in Product Calculations
Products of two integers can exceed the 32-bit integer range, especially when values approach 10^5 in magnitude. Always use 64-bit integers (long long in C++, long in Java) for product calculations and comparisons. Failing to do so causes incorrect counts and wrong answers.
Incorrect Handling of Negative Numbers
When one or both arrays contain negative numbers, the sign of the product flips, and the ordering reverses. A negative number multiplied by a large positive yields a more negative (smaller) result. You must handle negative-negative, negative-positive, positive-negative, and positive-positive cases separately to count products correctly.
Incorrect Floor/Ceiling Division for Negative Values
Standard integer division truncates toward zero, but counting products requires floor division for positive divisors and ceiling logic for negative divisors. Using the wrong rounding direction causes off-by-one errors in binary search bounds. Use language-specific floor division functions or manually adjust for negative operands.
Not Accounting for Zero Values
When an element is zero, its product with any number is zero. This affects counting: if the target product is non-negative, all pairs involving zero contribute to the count. Forgetting to handle zeros separately leads to missing or double-counting products.
Binary Search Boundary Errors
The search range must cover all possible products, from the most negative to the most positive. Setting bounds too tight causes the algorithm to miss the answer. Use safe bounds like -10^10 to 10^10 based on the problem constraints, and ensure the binary search condition correctly finds the smallest value with at least k products less than or equal to it.
Python code example
from typing import List
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
n1, n2 = len(nums1), len(nums2)
pos1 = 0 # first non-negative in nums1
while pos1 < n1 and nums1[pos1] < 0:
pos1 += 1
pos2 = 0 # first non-negative in nums2
while pos2 < n2 and nums2[pos2] < 0:
pos2 += 1
def count(prod):
cnt = 0
# negative * negative -> positive
i, j = 0, pos2 - 1
while i < pos1 and j >= 0:
if nums1[i] * nums2[j] > prod:
i += 1
else:
cnt += (pos1 - i)
j -= 1
# positive * positive -> positive
i, j = pos1, n2 - 1
while i < n1 and j >= pos2:
if nums1[i] * nums2[j] > prod:
j -= 1
else:
cnt += (j - pos2 + 1)
i += 1
# negative * positive -> negative
i, j = 0, pos2
while i < pos1 and j < n2:
if nums1[i] * nums2[j] > prod:
j += 1
else:
cnt += (n2 - j)
i += 1
# positive * negative → negative
i, j = pos1, 0
while i < n1 and j < pos2:
if nums1[i] * nums2[j] > prod:
i += 1
else:
cnt += (n1 - i)
j += 1
return cnt
left, right = -10**10, 10**10
while left <= right:
mid = (left + right) // 2
if count(mid) < k:
left = mid + 1
else:
right = mid - 1
return left
C++ code example
class Solution {
public:
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
int n1 = nums1.size(), n2 = nums2.size();
int pos1 = 0; // first non-negative in nums1
while (pos1 < n1 && nums1[pos1] < 0) {
pos1++;
}
int pos2 = 0; // first non-negative in nums2
while (pos2 < n2 && nums2[pos2] < 0) {
pos2++;
}
long long left = -10000000000LL, right = 10000000000LL;
while (left <= right) {
long long mid = left + (right - left) / 2;
if (count(nums1, nums2, pos1, pos2, n1, n2, mid) < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
private:
long long count(const vector<int>& nums1, const vector<int>& nums2,
int pos1, int pos2, int n1, int n2,
long long prod) {
long long cnt = 0;
// negative * negative -> positive
int i = 0, j = pos2 - 1;
while (i < pos1 && j >= 0) {
if ((long long)nums1[i] * nums2[j] > prod) {
i++;
} else {
cnt += (pos1 - i);
j--;
}
}
// positive * positive -> positive
i = pos1; j = n2 - 1;
while (i < n1 && j >= pos2) {
if ((long long)nums1[i] * nums2[j] > prod) {
j--;
} else {
cnt += (j - pos2 + 1);
i++;
}
}
// negative * positive -> negative
i = 0; j = pos2;
while (i < pos1 && j < n2) {
if ((long long)nums1[i] * nums2[j] > prod) {
j++;
} else {
cnt += (n2 - j);
i++;
}
}
// positive * negative -> negative
i = pos1; j = 0;
while (i < n1 && j < pos2) {
if ((long long)nums1[i] * nums2[j] > prod) {
i++;
} else {
cnt += (n1 - i);
j++;
}
}
return cnt;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.