Kth Smallest Product of Two Sorted Arrays in Java

2 May 2025 | 4 min read

Given two sorted integer arrays, nums1 and nums2, and an integer k. The task is to determine the kth (-based) least product of nums1[i] * nums2[j], where 0 <= i < nums1.length and 0 <= j < nums2.length.

Example 1:

Input:

nums1 = [2,8], nums2 = [3,4,5], k = 4

Output: 24

Explanation: Four products that are less than or equal to 24 are possible:

2 * 3 = 6

2 * 4 = 8

2 * 5 = 10

8 * 3 = 24

Example 2:

Input:

nums1 = [-5,-3,0,3], nums2 = [2,4], k = 6

Output: 0

Explanation: There are 6 possible products that are less than or equal to 0:

-5*2=-10

-5*4=-20

-3*2=-6

-3*4=-12

0*2=0

0*4=0

Example 3:

Input:

nums1 = [-6,-4,-3,0,1,3,4,7], nums2 = [-5,2,3,4], k = 40

Output: 147

Brute Force Approach

ALGORITHM:

Step 1: To store the products of components A and B, create an empty list called products.

Step 2: Iterate over every element in A. Add a * b to products for every an as you iterate through each element b in B.

Step 3: Use Collections. Sort to arrange the product list in ascending order.

Step 4: Go to index k-1 in products to get the kth smallest product. Return products.get(k - 1) as the outcome.

Implementation:

The implementation of the above steps given below

FileName: KthSmallestProduct.java

Output:

 
Kth Smallest Product is: 6

Complexity Analysis:

Time Complexity: O(m⋅log (m⋅n)) is the time complexity. It takes O(m⋅n) to generate all products and O(m⋅log (m⋅n)) to sort them.

Space Complexity: O(m⋅n) space is needed to store all m⋅n products in the products list.

Optimal Approach

We can utilize binary search on the potential product values to find the best answer.

ALGORITHM:

Step 1: First, set the leftmost product (A[0] * B[0]) to the left and the most prominent product (A[m-1] * B[n-1]) to the right. Here, m and n stand for the lengths of A and B, respectively.

Step 2: As left is less than right in step two:

Determine mid by taking the middle of left and right. To determine how many items are fewer than or equal to mid, use the helper function countLessThanOrEqual. Adjust left to mid + 1 if the count is less than k and right to mid otherwise. The kth most miniature products will be on the left after the loop ends.

Step 3: For every element in A, count the products that are less than or equal to mid.

Step 3.1: Use the upper bound to count entries in B that are less than or equal to x/a if a > 0.
Step 3.2: Use lower bound to count entries in B that are higher than or equal to x/a if a < 0.
Step 3.3: Since every product with zero is zero, add the length of B if a == 0 and x >= 0.

Give back the total number of an in A.

Step 4: Finding the first location in B where elements are more significant than x. Binary Search for Bounds in B, upper bound. Lower-bound identifies the first place in B where at least x items are present.

Implementation:

The implementation of the above steps given below

FileName: KthSmallestProduct1.java

Output:

 
Kth Smallest Product is: 6

Complexity Analysis:

Time Complexity: O((m+n)log(max range)) It takes O(log(max range)) to perform a binary search on the product range and O(m+n) to count elements that are smaller than or equal to mid.

Space Complexity: O(1) Only a fixed quantity of additional space is utilized.

Next TopicNo Suitable Driver Found For JDBC

← prev next →