LeetCode Daily Challenge-2040. Kth Smallest Product of Two Sorted Arrays(Hard)


- π Date: June 25, 2025
- π§Ή Problem: Given two sorted arrays, find the k-th smallest product that can be formed by multiplying one element from each array.
- π LeetCode link
- π·οΈ Tags: Binary Search, Two Pointers, Math
π Problem Summary
You're given two sorted arrays nums1
and nums2
, possibly with negative numbers.
You are to return the k-th smallest product of the form nums1[i] * nums2[j]
.
π‘ Key Insight
We want to find the k
-th smallest element in a virtual sorted array formed by all nums1[i] * nums2[j]
, without actually generating all products (which would be too slow for large arrays).
π‘ Approach
We use binary search over the value space, not index space.
- The search space is the possible product values: from
-10^10
to+10^10
. - For a guessed value
mid
, we count how many products are β€mid
. - If the count is less than
k
, increasemid
; else, try a smaller value. - The helper function
f()
computes how many products for a fixednums1[i]
are β€mid
.
β Python Code
from bisect import bisect_right, bisect_left
from typing import List
class Solution:
def f(self, nums2: List[int], x1: int, v: int) -> int:
if x1 > 0:
return bisect_right(nums2, v // x1)
elif x1 < 0:
return len(nums2) - bisect_left(nums2, -(-v // x1))
else:
return len(nums2) if v >= 0 else 0
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
n1 = len(nums1)
left, right = -(10**10), 10**10
while left <= right:
mid = (left + right) // 2
count = 0
for i in range(n1):
count += self.f(nums2, nums1[i], mid)
if count < k:
left = mid + 1
else:
right = mid - 1
return left
π Function Breakdown
f(nums2, x1, v)
This function calculates how many values in nums2
form a product with x1
that is β€ v
.
- If
x1 > 0
, we wantx1 * x2 β€ v
βx2 β€ v // x1
- If
x1 < 0
, we wantx2 β₯ ceil(v / x1)
(sincex1
is negative) β use-(-v // x1)
to compute ceiling division - If
x1 == 0
, all products are0
, which is β€v
ifv β₯ 0
, so we return all ofnums2
Main binary search
We use left
and right
to perform value-based binary search on the range [-1e10, 1e10]
.
At each step:
- We count how many products are
β€ mid
- If count is less than
k
, we need to search higher - Otherwise, we continue searching lower to find the smallest possible value that satisfies the condition
π Complexity
Time:
O(N log(M) log(R))
N = len(nums1)
,M = len(nums2)
R
is the product range (2 * 10^10
), so log(R) β 60
- Space:
O(1)
additional space
πͺ Example
nums1 = [-4, -2, 0, 3]
nums2 = [-2, -1, 1, 2]
k = 8
Products (sorted):
[-8, -4, -4, -3, -2, -2, -1, 0, 0, 0, 1, 2, 2, 3, 4, 6]
β The 8th smallest is: 0
β
The code correctly returns 0
.
π Summary
Part | Meaning |
find kth product | Use binary search on value space |
f() | Counts how many products are β€ mid for each nums1[i] |
-(-v // x1) | Python trick for ceiling division |
bisect | Fast way to search sorted arrays |
Handles negatives | Separate cases for positive/negative/zero |
π Final Thoughts
This is a great example of how binary search can be used not just on arrays, but on the answer itself. Mastering this βbinary search on resultβ pattern is essential for tackling advanced algorithm problems.
Subscribe to my newsletter
Read articles from Anni Huang directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by

Anni Huang
Anni Huang
I am Anni HUANG, a software engineer with 3 years of experience in IDE development and Chatbot.