LeetCode 2040: Kth Smallest Product of Two Sorted Arrays Solution

Master LeetCode problem 2040 (Kth Smallest Product of Two Sorted Arrays), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2040. Kth Smallest Product of Two Sorted Arrays

Hard

Array Binary Search

Problem Explanation

Explanation

To solve this problem, we can use a binary search on the possible range of products. We need to find the kth smallest product of two numbers from the sorted arrays nums1 and nums2. We can guess a product and count how many pairs of numbers from the arrays have a product less than or equal to that guessed product. Based on this count, we can adjust our guess by binary searching the possible range of products.

Algorithm:

Initialize the lower bound as the minimum product of the two arrays and the upper bound as the maximum product of the two arrays.
Perform a binary search on the possible range of products.
In each iteration, guess the mid value of the range and count how many pairs of numbers have a product less than or equal to the guessed value.
Update the lower or upper bound based on the count obtained.
Continue this process until the lower bound is equal to the upper bound.
Return the lower bound as the kth smallest product.

Time Complexity:

The time complexity of this algorithm is O(n * log(M)), where n is the length of the arrays and M is the maximum product possible.

Space Complexity:

The algorithm uses constant space, so the space complexity is O(1).

Solution Code

class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, int k) {
        long left = Long.MIN_VALUE, right = Long.MAX_VALUE;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = countPairs(nums1, nums2, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private long countPairs(int[] nums1, int[] nums2, long target) {
        long count = 0;
        int j = nums2.length - 1;
        
        for (int i = 0; i < nums1.length; i++) {
            while (j >= 0 && (long) nums1[i] * nums2[j] > target) {
                j--;
            }
            count += j + 1;
        }
        
        return count;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2040 (Kth Smallest Product of Two Sorted Arrays)?

This page provides optimized solutions for LeetCode problem 2040 (Kth Smallest Product of Two Sorted Arrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

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

The time complexity for LeetCode 2040 (Kth Smallest Product of Two Sorted Arrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2040 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2040 in Java, C++, or Python.

Back to LeetCode Solutions