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

Anni HuangAnni Huang
3 min read
  • πŸ“… 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.

  1. The search space is the possible product values: from -10^10 to +10^10.
  2. For a guessed value mid, we count how many products are ≀ mid.
  3. If the count is less than k, increase mid; else, try a smaller value.
  4. The helper function f() computes how many products for a fixed nums1[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 want x1 * x2 ≀ v β†’ x2 ≀ v // x1
  • If x1 < 0, we want x2 β‰₯ ceil(v / x1) (since x1 is negative) β†’ use -(-v // x1) to compute ceiling division
  • If x1 == 0, all products are 0, which is ≀ v if v β‰₯ 0, so we return all of nums2

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

PartMeaning
find kth productUse binary search on value space
f()Counts how many products are ≀ mid for each nums1[i]
-(-v // x1)Python trick for ceiling division
bisectFast way to search sorted arrays
Handles negativesSeparate 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.

0
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.