Solution: Kth Smallest Product of Two Sorted Arrays

Explore how to use a modified binary search to find the kth smallest product formed by pairs from two sorted arrays. Understand how to handle negative numbers and zeros, implement counting with binary search for feasibility checks, and achieve an efficient solution with optimal 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$ ...