What is the time complexity of LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?

The Python solution on this page runs in O(m \times \log n \times \log M), where m and n are the lengths of \textit{nums1} and \textit{nums2}, respectively, and M is the maximum absolute value in \textit{nums1} and \textit{nums2}.

What is the space complexity of LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?

The Python solution on this page uses O(1) auxiliary space.

Kth Smallest Product of Two Sorted Arrays — LeetCode 2040 Python Solution

Q: How hard is LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?

LeetCode 2040. Kth Smallest Product of Two Sorted Arrays is rated Hard on LeetCode.

Q: What topics does LeetCode 2040. Kth Smallest Product of Two Sorted Arrays cover?

LeetCode 2040. Kth Smallest Product of Two Sorted Arrays is tagged Array and Binary Search on LeetCode.

HardArrayBinary Search

Problem: #2040
Pattern: Monotonic Stack
Reading time: 3 min
Source: leetcode.com

The problem

Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the kth (1-based) smallest product of nums1[i] \* nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.

Example

Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:

Python solution

Python

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count(p: int) -> int:
            cnt = 0
            n = len(nums2)
            for x in nums1:
                if x > 0:
                    cnt += bisect_right(nums2, p / x)
                elif x < 0:
                    cnt += n - bisect_left(nums2, p / x)
                else:
                    cnt += n * int(p >= 0)
            return cnt

        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))
        return bisect_left(range(-mx, mx + 1), k, key=count) - mx

Complexity

Measure	Complexity
Time	O(m \times \log n \times \log M), where m and n are the lengths of \textit{nums1} and \textit{nums2}, respectively, and M is the maximum absolute value in \textit{nums1} and \textit{nums2}
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 2040. Kth Smallest Product of Two Sorted Arrays is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?: LeetCode 2040. Kth Smallest Product of Two Sorted Arrays is rated Hard on LeetCode.
What is the time complexity of LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?: The Python solution on this page runs in O(m \times \log n \times \log M), where m and n are the lengths of \textit{nums1} and \textit{nums2}, respectively, and M is the maximum absolute value in \textit{nums1} and \textit{nums2}.
What is the space complexity of LeetCode 2040. Kth Smallest Product of Two Sorted Arrays?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2040. Kth Smallest Product of Two Sorted Arrays cover?: LeetCode 2040. Kth Smallest Product of Two Sorted Arrays is tagged Array and Binary Search on LeetCode.