Skip to main content
Talentd

Kth Smallest Product of Two Sorted Arrays - Solution & Explanation

HardArrayBinary Search30 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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 1:

Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2nd smallest product is 8.

Example 2:

Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0
Explanation: The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6th smallest product is 0.

Example 3:

Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6
Explanation: The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3rd smallest product is -6.

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 5 * 104
  • -105 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= nums1.length * nums2.length
  • nums1 and nums2 are sorted.

Approach Overview

Problem Overview: You are given two sorted arrays and an integer k. The task is to find the kth smallest value among all possible products formed by multiplying one element from each array. The challenge comes from negative numbers, zeros, and large value ranges, which make naive enumeration impractical.

Approach 1: Using Min-Heap for Kth Smallest Product (O(k log n) time, O(n) space)

This method treats the multiplication pairs similarly to merging sorted lists. Because both arrays are sorted, the smallest products involving each element of nums1 can be pushed into a min-heap. Each heap entry stores the current product along with the indices used to generate it. When you pop the smallest product, push the next candidate product for that index pair. This approach iteratively extracts the next smallest product until the kth one appears. It works well when k is relatively small compared to n × m. The heap ensures each extraction costs O(log n) while preserving sorted order of candidate products.

Approach 2: Binary Search on Possible Products (O((n + m) log R) time, O(1) space)

The optimal solution searches the answer directly instead of generating products. Define a product range from the smallest possible multiplication to the largest. Perform binary search on this range and check how many pairs produce a value ≤ mid. Counting pairs efficiently relies on the arrays being sorted. For each element in the first array, determine how many elements in the second array produce products ≤ mid using pointer movement or binary search. Careful handling of negative numbers is required because the inequality direction flips when multiplying by negatives. This counting step runs in linear time across both arrays. If the count is at least k, move the search space left; otherwise move right. The final boundary gives the kth smallest product.

The binary search strategy leverages properties of sorted arrays and avoids generating all combinations. Instead of computing n × m products, it repeatedly counts how many fall within a threshold value.

Recommended for interviews: Interviewers typically expect the binary search on answer technique. The heap approach shows understanding of kth-element problems, but it struggles with very large product spaces. The binary search solution demonstrates stronger algorithmic reasoning and efficient use of sorted arrays with binary search counting.

Approach 1: Using Min-Heap for Kth Smallest Product

The intuitive approach is to leverage a min-heap to track the smallest products as we iterate over the possible products. We can maintain a heap of size k to ensure that we can always access the kth smallest element efficiently after processing.

This approach involves iterating through each possible product, inserting it into a min-heap, and once the heap grows beyond size k, we pop the smallest element until we are left with a heap that contains exactly k elements, the largest of which is our kth smallest product.

In this Python solution, we use a min-heap to keep track of the smallest products. We iterate over each pair of numbers from nums1 and nums2, calculate the product, and push it into the heap. If the heap exceeds size k, the smallest element is popped, ensuring that the heap retains only the k smallest elements. The k-th smallest product is obtained by popping the heap.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(m * n * log(k)), where m and n are the lengths of nums1 and nums2 respectively.
Space Complexity: O(k) for the heap.

Try this approach in the editor →

Approach 2: Binary Search on Possible Products

An advanced, optimized approach employs binary search to efficiently find the k-th smallest product. The idea is to leverage the sorted nature of the arrays and conduct binary search over the range of possible products.

Binary search is performed on the range from the smallest possible product (min(nums1)*min(nums2)) to the largest possible product (max(nums1)*max(nums2)). For each midpoint value, count the number of products which are less than or equal to this midpoint. Adjust the binary search bounds based on this count to isolate the k-th smallest product eventually.

In the Python version, we set up a binary search range between the minimum and maximum possible products. Using a helper function, count_less_equal, we count for each potential midpoint how many products are less than or equal to the midpoint. By determining whether this count meets 'k', we adjust our search range iteratively to home in on the k-th smallest product.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O((m + n) * log(U)), where m and n are the lengths of the arrays and U is the product value range.
Space Complexity: O(1), as it uses constant space.

Try this approach in the editor →

Approach 3: Binary Search

We can use binary search to enumerate the value of the product p, defining the binary search interval as [l, r], where l = -max(|nums1[0]|, |nums1[n - 1]|) times max(|nums2[0]|, |nums2[n - 1]|), r = -l.

For each p, we calculate the number of products less than or equal to p. If this number is greater than or equal to k, it means the k-th smallest product must be less than or equal to p, so we can reduce the right endpoint of the interval to p. Otherwise, we increase the left endpoint of the interval to p + 1.

The key to the problem is how to calculate the number of products less than or equal to p. We can enumerate each number x in nums1 and discuss in cases:

  • If x > 0, then x times nums2[i] is monotonically increasing as i increases. We can use binary search to find the smallest i such that x times nums2[i] > p. Then, i is the number of products less than or equal to p, which is accumulated into the count cnt;
  • If x < 0, then x times nums2[i] is monotonically decreasing as i increases. We can use binary search to find the smallest i such that x times nums2[i] leq p. Then, n - i is the number of products less than or equal to p, which is accumulated into the count cnt;
  • If x = 0, then x times nums2[i] = 0. If p geq 0, then n is the number of products less than or equal to p, which is accumulated into the count cnt.

This way, we can find the k-th smallest product through binary search.

The time complexity is O(m times log n times log M), where m and n are the lengths of nums1 and nums2, respectively, and M is the maximum absolute value in nums1 and nums2.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Min-Heap for Kth Smallest Product

Time Complexity: O(m * n * log(k)), where m and n are the lengths of nums1 and nums2 respectively.
Space Complexity: O(k) for the heap.

Binary Search on Possible Products

Time Complexity: O((m + n) * log(U)), where m and n are the lengths of the arrays and U is the product value range.
Space Complexity: O(1), as it uses constant space.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap for Kth ProductO(k log n)O(n)When k is small and you want a straightforward kth-element extraction approach
Binary Search on Product RangeO((n + m) log R)O(1)Best for large arrays or large k; avoids generating all pair products

Video Solution

Kth Smallest Product of Two Sorted Arrays | Detailed Explanation | Leetcode 2040 | codestorywithMIK • codestorywithMIK • 13,211 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Smallest Product of Two Sorted Arrays easy or hard?
The problem is classified as Hard because it combines multiple tricky aspects: binary search on answer space, handling negative numbers in multiplication comparisons, and counting valid pairs efficiently. Many candidates first attempt brute force before discovering the binary search counting strategy.
Kth Smallest Product of Two Sorted Arrays Python/Java solution
Most implementations use binary search over the product range and a counting function to determine how many pairs produce values less than or equal to a threshold. This approach works efficiently in Python, Java, and C++ because it only scans the arrays during each binary search step instead of generating all products.
What is the best approach for Kth Smallest Product of Two Sorted Arrays?
The most efficient approach is binary search on the product range. Instead of computing every product, the algorithm guesses a value and counts how many pairs produce products less than or equal to it. Because both arrays are sorted, this counting step runs in linear time. The overall complexity becomes O((n + m) log R), where R is the range of possible products.
How to solve Kth Smallest Product of Two Sorted Arrays in O((n+m) log R)?
Use binary search on the range of possible products. For each candidate value mid, count how many pairs from the two sorted arrays produce a product ≤ mid. This count is computed by iterating through one array and using pointer movement or binary search on the second array while handling negative numbers carefully. Adjust the search range until the kth smallest product is found.
Is Kth Smallest Product of Two Sorted Arrays asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it combines binary search on answers with careful handling of negative numbers and sorted arrays. It tests reasoning about search spaces rather than direct enumeration of pairs.
What data structure is used in Kth Smallest Product of Two Sorted Arrays?
Two main techniques appear in solutions: a min-heap (priority queue) for incremental extraction of the next smallest product, and binary search on the value range combined with two-pointer or binary-search counting across sorted arrays. The optimal solution primarily relies on binary search logic.
What is the time complexity of Kth Smallest Product of Two Sorted Arrays?
The optimal binary search solution runs in O((n + m) log R) time and O(1) extra space, where R is the difference between the minimum and maximum possible product values. A heap-based approach can solve it in O(k log n) time with O(n) space but becomes inefficient when k is large.

Ready to solve this problem?

Practice Kth Smallest Product of Two Sorted Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find K Pairs with Smallest Sums

Next

K-diff Pairs in an Array