Kth Smallest Product of Two Sorted Arrays
Real-world version: The k-th Smallest Product of Two ListsThe statement here is our own: the same inputs, outputs and technique.
Two lists of readings are given as nums1 and nums2, each already in non-decreasing order. Either may hold negative readings.
Take every product of one reading from the first list with one from the second, keeping every combination of positions even when the products repeat. Return the k-th smallest of those products, counting from one.
Examples
Example 1
- Input
- nums1 = [-4, -2, 0, 3], nums2 = [-5, 1, 6], k = 7
- Output
- 0
The twelve products in order run -24, -12, -10, -6, -5, -2, 0, 0, 0, 3, 18 and 20, so the seventh is nothing.
Example 2
- Input
- nums1 = [-1], nums2 = [1], k = 1
- Output
- -1
The only product is a negative reading times a positive one.
Example 3
- Input
- nums1 = [2, 5], nums2 = [3, 4], k = 2
- Output
- 8
The four products are 6, 8, 15 and 20, so the second is 8.
Constraints
- 1 <= nums1.length <= 5 * 10^4
- 1 <= nums2.length <= 5 * 10^4
- -10^5 <= nums1[i] <= 10^5
- -10^5 <= nums2[i] <= 10^5
- 1 <= k <= nums1.length * nums2.length
- nums1 and nums2 are each in non-decreasing order
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def kth_smallest_product(nums1: list[int], nums2: list[int], k: int) -> int:public long kthSmallestProduct(int[] nums1, int[] nums2, long k)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's