Solution: Kth Smallest Product of Two Sorted Arrays

Understand how to find the kth smallest product of two sorted integer arrays using an advanced binary search technique. This lesson teaches you to count products without enumerating them explicitly, leveraging sorted arrays and binary search for efficient computation. You will learn how to implement a helper function that counts products less than a target and apply a binary search over the search space, optimizing both time and space complexity.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given two sorted $0$ -indexed integer arrays nums1 and nums2, along with an integer k.

Consider all possible products formed by nums1[i] * nums2[j], where i ranges over all valid indices of nums1 and j ranges over all valid indices of nums2. Return the $k^{th}$ smallest product among all such pairs, using $1$ -based indexing.

Note: Both nums1 and nums2 are sorted in non-decreasing order. The arrays may contain negative numbers and zero, so the products can be negative, zero, or positive.

Constraints:

$1 \leq$ nums1.length, nums2.length $\leq 5 \times 10^4$
$-10^5 \leq$ nums1[i], nums2[j] $\leq 10^5$ ...