⚡Flashcard Drill➔
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

  1. Binary search on the product value x: "how many pairs have product at most x" is monotone in x.
  2. For each element a of nums1, the valid partners in the sorted nums2 form a prefix or a suffix depending on the sign of a.
  3. For a > 0, count b <= x / a via bisect_right; for a < 0, count b >= ceil(x / a) via bisect_left; for a == 0, all pairs count when x >= 0.
  4. 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 negative a the inequality flips, so the valid partners form a suffix rather than a prefix.
  • Using x // a for negative a: Python's floor division rounds toward negative infinity, so the ceiling must be computed as -((-x) // a).
  • Forgetting the a == 0 case: the product is 0, which is at most x exactly when x >= 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems