NeetCode #301LC-2040HardBinary Search
← Back to All Problems#301 · #2040 · Kth Smallest Product of Two Sorted Arrays(两个有序数组的第 K 小乘积)
📌 Problem Statement & Constraints
Given two sorted arrays
nums1 and nums2 and an integer k, return the k-th smallest product among all nums1[i] * nums2[j]. Constraints: 1 <= nums1.length, nums2.length <= 5 * 10^4, -10^5 <= nums1[i], nums2[j] <= 10^5, 1 <= k <= nums1.length * nums2.length.💡 Core Algorithmic Approaches
- Binary search on the product value
x: "how many pairs have product at mostx" is monotone inx. - For each element
aofnums1, the valid partners in the sortednums2form a prefix or a suffix depending on the sign ofa. - For
a > 0, countb <= x / aviabisect_right; fora < 0, countb >= ceil(x / a)viabisect_left; fora == 0, all pairs count whenx >= 0. - The sign handling is the crux: dividing by a negative number flips the inequality.
💻 Benchmark Python3 Implementation
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
from bisect import bisect_left, bisect_right
n2 = len(nums2)
def count(x: int) -> int:
"""number of pairs with product <= x"""
cnt = 0
for a in nums1:
if a > 0:
cnt += bisect_right(nums2, x // a) # b <= floor(x / a)
elif a < 0:
# a * b <= x <=> b >= ceil(x / a) (dividing flips the sign)
need = -((-x) // a) # ceil(x / a)
cnt += n2 - bisect_left(nums2, need)
else:
if x >= 0:
cnt += n2 # 0 <= x
return cnt
# candidate product range from the four extreme corners
cands = [nums1[0] * nums2[0], nums1[0] * nums2[-1],
nums1[-1] * nums2[0], nums1[-1] * nums2[-1]]
lo, hi = min(cands), max(cands)
while lo < hi:
mid = (lo + hi) // 2
if count(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + m) log(range)): each counting pass is O(n log m) via binary search.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Ignoring the sign of
a: for negativeathe inequality flips, so the valid partners form a suffix rather than a prefix. - Using
x // afor negativea: Python's floor division rounds toward negative infinity, so the ceiling must be computed as-((-x) // a). - Forgetting the
a == 0case: the product is 0, which is at mostxexactly whenx >= 0. - Setting the search range to
[min product, max product]incorrectly: the extremes are always achieved at the corners of the two arrays, hence the four candidates. - Enumerating all products: up to 2.5 * 10^9 pairs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.