Kth Smallest Product of Two Sorted Arrays solution and explanation
Google
9 more videos on this problem
Kth Smallest Product of Two Sorted Arrays | Detailed Explanation | Leetcode 2040 | codestorywithMIKcodestorywithMIK · 59:31 · 13K views
Kth Smallest Product of Two Sorted Arrays| LeetCode 2040| Daily Leetcode potd | binary search dsaCode Thoughts · 16:34 · 3K views
2040. Kth Smallest Product of Two Sorted Arrays | Leetcode Daily - PythonLeetcode Daily · 6:41 · 2K views
2040. Kth Smallest Product of Two Sorted Arrays (Leetcode Hard)Programming Live with Larry · 1:01:49 · 2K views
LeetCode 2040. Kth Smallest Product of Two Sorted ArraysKacy Codes · 40:36 · 1K views
LeetCode 2040 Kth Smallest Product of Two Sorted Arrays | Binary Search on Answers | Hard | GoogleCode Harmony · 31:11 · 1K views
Leetcode 2040. Kth Smallest Product of Two Sorted Arrays | Binary Search + Math IntuitionStatLearn Tech · 31:03 · 782 views
2040. Kth Smallest Product of Two Sorted Arrays | leetcode - 2040 | java solutioncodingX krishna · 47:08 · 464 views
Kth Smallest Product of Two Sorted Arrays - Google/Amazon/Apple Interview Question - Leetcode 2040Engineering with Temi · 22:03 · 133 views
Day 418: LeetCode Problem 2040. Kth Smallest Product of Two Sorted Arrays - SwiftiOSxBank · 22:21 · 122 views
The problem
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] <= 1051 <= k <= nums1.length * nums2.lengthnums1andnums2are 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.
import heapq
def kth_smallest_product(nums1, nums2, k):
min_heap = []
for a in nums1:
for b in nums2:
heapq.heappush(min_heap, a * b)
if len(min_heap) > k:
heapq.heappop(min_heap)
return heapq.heappop(min_heap)
# Example Usage:
# nums1 = [2, 5], nums2 = [3, 4], k = 2
# Output: 8import java.util.PriorityQueue;
public class KthSmallestProduct {
public int kthSmallestProduct(int[] nums1, int[] nums2, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int a : nums1) {
for (int b : nums2) {
minHeap.offer(a * b);
if (minHeap.size() > k) {
minHeap.poll();
}
}
}
return minHeap.poll();
}
}
// Example Usage:
// int[] nums1 = {2, 5};
// int[] nums2 = {3, 4};
// int k = 2;
// new KthSmallestProduct().kthSmallestProduct(nums1, nums2, k);#include <queue>
#include <vector>
#include <functional>
using namespace std;
int kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int a : nums1) {
for (int b : nums2) {
minHeap.push(a * b);
if (minHeap.size() > k) {
minHeap.pop();
}
}
}
return minHeap.top();
}
// Example Usage:
// vector<int> nums1 = {2, 5};
// vector<int> nums2 = {3, 4};
// int k = 2;
// cout << kthSmallestProduct(nums1, nums2, k);function kthSmallestProduct(nums1, nums2, k) {
let minHeap = [];
for (let a of nums1) {
for (let b of nums2) {
let product = a * b;
if (minHeap.length < k) {
minHeap.push(product);
minHeap.sort((x, y) => y - x);
} else if (product < minHeap[0]) {
minHeap[0] = product;
minHeap.sort((x, y) => y - x);
}
}
}
return minHeap[0];
}
// Example Usage:
// const nums1 = [2, 5];
// const nums2 = [3, 4];
// const k = 2;
// console.log(kthSmallestProduct(nums1, nums2, k));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int kthSmallestProduct(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
int* products = malloc(nums1Size * nums2Size * sizeof(int));
int index = 0;
for (int i = 0; i < nums1Size; i++) {
for (int j = 0; j < nums2Size; j++) {
products[index++] = nums1[i] * nums2[j];
}
}
qsort(products, index, sizeof(int), cmp);
int result = products[k - 1];
free(products);
return result;
}
// Example Usage:
// int nums1[] = {2, 5}; int nums2[] = {3, 4};
// int result = kthSmallestProduct(nums1, 2, nums2, 2, 2);
// printf("%d\n", result);using System;
using System.Collections.Generic;
public class KthSmallestProduct {
public int FindKthSmallestProduct(int[] nums1, int[] nums2, int k) {
SortedSet<Tuple<int, int, int>> minHeap = new SortedSet<Tuple<int, int, int>>();
for (int i = 0; i < nums1.Length; i++) {
for (int j = 0; j < nums2.Length; j++) {
int product = nums1[i] * nums2[j];
minHeap.Add(new Tuple<int, int, int>(product, i, j));
if (minHeap.Count > k) {
minHeap.Remove(minHeap.Max);
}
}
}
return minHeap.Max.Item1;
}
}
// Example Usage:
// var nums1 = new int[] { 2, 5 };
// var nums2 = new int[] { 3, 4 };
// var result = new KthSmallestProduct().FindKthSmallestProduct(nums1, nums2, 2);
// Console.WriteLine(result);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.
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.
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.
def kth_smallest_product(nums1, nums2, k):
low, high = nums1[0] * nums2[0], nums1[-1] * nums2[-1]
def count_less_equal(x):
count, j = 0, len(nums2) - 1
for i in range(len(nums1)):
while j >= 0 and nums1[i] * nums2[j] > x:
j -= 1
count += (j + 1)
return count
while low < high:
mid = (low + high) // 2
if count_less_equal(mid) < k:
low = mid + 1
else:
high = mid
return low
# Example Usage:
# nums1 = [2, 5]
# nums2 = [3, 4]
# k = 2
# Output: 8public class KthSmallestProductBinarySearch {
public long kthSmallestProduct(int[] nums1, int[] nums2, int k) {
long low = (long) nums1[0] * nums2[0], high = (long) nums1[nums1.length - 1] * nums2[nums2.length - 1];
while (low < high) {
long mid = low + (high - low) / 2;
if (countLessEqual(nums1, nums2, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private int countLessEqual(int[] nums1, int[] nums2, long x) {
int count = 0, j = nums2.length - 1;
for (int num1 : nums1) {
while (j >= 0 && (long) num1 * nums2[j] > x) {
j--;
}
count += (j + 1);
}
return count;
}
}
// Example Usage:
// int[] nums1 = {2, 5};
// int[] nums2 = {3, 4};
// int k = 2;
// System.out.println(new KthSmallestProductBinarySearch().kthSmallestProduct(nums1, nums2, k));#include <vector>
#include <algorithm>
using namespace std;
long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, int k) {
long long low = nums1.front() * nums2.front();
long long high = nums1.back() * nums2.back();
auto countLessEqual = [&nums1, &nums2](long long x) {
int count = 0, j = nums2.size() - 1;
for (int i = 0; i < nums1.size(); ++i) {
while (j >= 0 && nums1[i] * nums2[j] > x) j--;
count += (j + 1);
}
return count;
};
while (low < high) {
long long mid = low + (high - low) / 2;
if (countLessEqual(mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Example Usage:
// vector<int> nums1 = {2, 5};
// vector<int> nums2 = {3, 4};
// int k = 2;
// cout << kthSmallestProduct(nums1, nums2, k);function kthSmallestProduct(nums1, nums2, k) {
let low = nums1[0] * nums2[0];
let high = nums1[nums1.length - 1] * nums2[nums2.length - 1];
const countLessEqual = (x) => {
let count = 0;
let j = nums2.length - 1;
for (let i = 0; i < nums1.length; i++) {
while (j >= 0 && nums1[i] * nums2[j] > x) {
j--;
}
count += j + 1;
}
return count;
};
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (countLessEqual(mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Example Usage:
// const nums1 = [2, 5];
// const nums2 = [3, 4];
// const k = 2;
// console.log(kthSmallestProduct(nums1, nums2, k));#include <limits.h>
#include <stdlib.h>
int countLessEqual(int* nums1, int nums1Size, int* nums2, int nums2Size, long long x) {
int count = 0, j = nums2Size - 1;
for (int i = 0; i < nums1Size; i++) {
while (j >= 0 && (long long)nums1[i] * nums2[j] > x) {
j--;
}
count += (j + 1);
}
return count;
}
long long kthSmallestProduct(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
long long low = (long long)nums1[0] * nums2[0], high = (long long)nums1[nums1Size-1] * nums2[nums2Size-1];
while (low < high) {
long long mid = low + (high - low) / 2;
if (countLessEqual(nums1, nums1Size, nums2, nums2Size, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Example Usage:
// int nums1[] = {2, 5}; int nums2[] = {3, 4};
// int result = kthSmallestProduct(nums1, 2, nums2, 2, 2);
// printf("%lld\n", result);public class KthSmallestProductBinarySearch {
public long FindKthSmallestProduct(int[] nums1, int[] nums2, int k) {
long low = (long)nums1[0] * nums2[0], high = (long)nums1[nums1.Length - 1] * nums2[nums2.Length - 1];
while (low < high) {
long mid = low + (high - low) / 2;
if (CountLessEqual(nums1, nums2, mid) < k) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
private int CountLessEqual(int[] nums1, int[] nums2, long x) {
int count = 0, j = nums2.Length - 1;
for (int i = 0; i < nums1.Length; i++) {
while (j >= 0 && (long)nums1[i] * nums2[j] > x) {
j--;
}
count += (j + 1);
}
return count;
}
}
// Example Usage:
// int[] nums1 = {2, 5};
// int[] nums2 = {3, 4};
// int k = 2;
// Console.WriteLine(new KthSmallestProductBinarySearch().FindKthSmallestProduct(nums1, nums2, k));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.
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.
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, thenx times nums2[i]is monotonically increasing asiincreases. We can use binary search to find the smallestisuch thatx times nums2[i] > p. Then,iis the number of products less than or equal top, which is accumulated into the countcnt; - If
x < 0, thenx times nums2[i]is monotonically decreasing asiincreases. We can use binary search to find the smallestisuch thatx times nums2[i] leq p. Then,n - iis the number of products less than or equal top, which is accumulated into the countcnt; - If
x = 0, thenx times nums2[i] = 0. Ifp geq 0, thennis the number of products less than or equal top, which is accumulated into the countcnt.
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.
function kthSmallestProduct(nums1: number[], nums2: number[], k: number): number {
const m = nums1.length;
const n = nums2.length;
const a = BigInt(Math.max(Math.abs(nums1[0]), Math.abs(nums1[m - 1])));
const b = BigInt(Math.max(Math.abs(nums2[0]), Math.abs(nums2[n - 1])));
let l = -a * b;
let r = a * b;
const count = (p: bigint): bigint => {
let cnt = 0n;
for (const x of nums1) {
const bx = BigInt(x);
if (bx > 0n) {
let l = 0,
r = n;
while (l < r) {
const mid = (l + r) >> 1;
const prod = bx * BigInt(nums2[mid]);
if (prod > p) {
r = mid;
} else {
l = mid + 1;
}
}
cnt += BigInt(l);
} else if (bx < 0n) {
let l = 0,
r = n;
while (l < r) {
const mid = (l + r) >> 1;
const prod = bx * BigInt(nums2[mid]);
if (prod <= p) {
r = mid;
} else {
l = mid + 1;
}
}
cnt += BigInt(n - l);
} else if (p >= 0n) {
cnt += BigInt(n);
}
}
return cnt;
};
while (l < r) {
const mid = (l + r) >> 1n;
if (count(mid) >= BigInt(k)) {
r = mid;
} else {
l = mid + 1n;
}
}
return Number(l);
}func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
m := len(nums1)
n := len(nums2)
a := max(abs(nums1[0]), abs(nums1[m-1]))
b := max(abs(nums2[0]), abs(nums2[n-1]))
r := int64(a) * int64(b)
l := -r
count := func(p int64) int64 {
var cnt int64
for _, x := range nums1 {
if x > 0 {
l, r := 0, n
for l < r {
mid := (l + r) >> 1
if int64(x)*int64(nums2[mid]) > p {
r = mid
} else {
l = mid + 1
}
}
cnt += int64(l)
} else if x < 0 {
l, r := 0, n
for l < r {
mid := (l + r) >> 1
if int64(x)*int64(nums2[mid]) <= p {
r = mid
} else {
l = mid + 1
}
}
cnt += int64(n - l)
} else if p >= 0 {
cnt += int64(n)
}
}
return cnt
}
for l < r {
mid := (l + r) >> 1
if count(mid) >= k {
r = mid
} else {
l = mid + 1
}
}
return l
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn kth_smallest_product(nums1: Vec<i32>, nums2: Vec<i32>, k: i64) -> i64 {
let m = nums1.len();
let n = nums2.len();
let a = nums1[0].abs().max(nums1[m - 1].abs()) as i64;
let b = nums2[0].abs().max(nums2[n - 1].abs()) as i64;
let mut l = -a * b;
let mut r = a * b;
let count = |p: i64| -> i64 {
let mut cnt = 0i64;
for &x in &nums1 {
if x > 0 {
let mut left = 0;
let mut right = n;
while left < right {
let mid = (left + right) / 2;
if (x as i64) * (nums2[mid] as i64) > p {
right = mid;
} else {
left = mid + 1;
}
}
cnt += left as i64;
} else if x < 0 {
let mut left = 0;
let mut right = n;
while left < right {
let mid = (left + right) / 2;
if (x as i64) * (nums2[mid] as i64) <= p {
right = mid;
} else {
left = mid + 1;
}
}
cnt += (n - left) as i64;
} else if p >= 0 {
cnt += n as i64;
}
}
cnt
};
while l < r {
let mid = l + (r - l) / 2;
if count(mid) >= k {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap for Kth Product | O(k log n) | O(n) | When k is small and you want a straightforward kth-element extraction approach |
| Binary Search on Product Range | O((n + m) log R) | O(1) | Best for large arrays or large k; avoids generating all pair products |
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.