Kth Smallest Product of Two Sorted Arrays
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to generate all possible products, store them in a list, sort the list, and then pick the k-th element. This method is simple to understand and implement but is highly inefficient for the given constraints.
Algorithm
- Initialize an empty list,
products. - Iterate through each element
num1in thenums1array. - For each
num1, iterate through each elementnum2in thenums2array. - Calculate the product
p = (long)num1 * num2. - Add the product
pto theproductslist. - After iterating through all pairs, sort the
productslist in non-decreasing order. - The k-th smallest product is the element at index
k-1in the sorted list. Returnproducts.get(k-1).
Walkthrough
This method involves a nested loop to compute every possible product of pairs (nums1[i], nums2[j]). All these m * n products are stored in a dynamic array or list. Once all products are generated, the list is sorted numerically. The k-th smallest product is then simply the element at the (k-1)-th index of this sorted list (since k is 1-based).
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public long kthSmallestProduct(int[] nums1, int[] nums2, long k) { List<Long> products = new ArrayList<>(); for (int num1 : nums1) { for (int num2 : nums2) { products.add((long) num1 * num2); } } Collections.sort(products); return products.get((int) k - 1); }}Complexity
Time
O(m * n * log(m * n)). Generating all `m*n` products takes `O(m*n)` time. Sorting these products takes `O(m*n * log(m*n))` time.
Space
O(m * n), where `m` and `n` are the lengths of `nums1` and `nums2` respectively. This is required to store all possible products.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct.
Cons
Exceeds time limits for large inputs due to
O(m*n*log(m*n))complexity.Exceeds memory limits for large inputs as it requires storing
m*nproducts.
A more efficient approach is to use binary search on the answer. Instead of searching for the k-th product among the products themselves, we search for its value within the possible range of product values. For a guessed value mid, we can efficiently count how many products are less than or equal to mid. This count helps us narrow down the search space for the answer.
Algorithm
- Define a search range for the product values. A safe range is
[-10^10, 10^10]. - Apply binary search on this range. Let the search variables be
lowandhigh. - In each step of the binary search, pick a
midvalue. - Count how many products
nums1[i] * nums2[j]are less than or equal tomid. Let this becount. - To calculate
count, iterate through each elementxinnums1:- If
x > 0, we needy <= mid / x. Use binary search onnums2to find the number of suchy. - If
x < 0, we needy >= mid / x. Use binary search onnums2to find the number of suchy. - If
x == 0, all products are0. Ifmid >= 0, addntocount.
- If
- If
count >= k, it meansmidcould be the answer, or the answer is smaller. So, we setans = midandhigh = mid - 1. - If
count < k,midis too small. We setlow = mid + 1. - The loop continues until
low > high. The finalansis the k-th smallest product.
Walkthrough
The range of possible products is from -10^5 * 10^5 = -10^10 to 10^5 * 10^5 = 10^10. We can binary search for the k-th smallest product's value in this range.
For a given value p, we need a function countLessEqual(p) that counts pairs (i, j) where nums1[i] * nums2[j] <= p. This function can be implemented by iterating through nums1 and, for each num1, using binary search on nums2 to find how many num2 values satisfy the condition. The condition num1 * num2 <= p transforms to num2 <= p / num1 if num1 > 0, and num2 >= p / num1 if num1 < 0.
class Solution { public long kthSmallestProduct(int[] nums1, int[] nums2, long k) { long low = -10000000001L; long high = 10000000001L; long ans = high; while (low <= high) { long mid = low + (high - low) / 2; if (countLessEqual(nums1, nums2, mid) >= k) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private long countLessEqual(int[] nums1, int[] nums2, long p) { long count = 0; for (int num1 : nums1) { if (num1 == 0) { if (p >= 0) { count += nums2.length; } } else if (num1 > 0) { count += countLE(nums2, (double) p / num1); } else { // num1 < 0 count += countGE(nums2, (double) p / num1); } } return count; } // Counts elements <= val in a sorted array private int countLE(int[] nums, double val) { int l = 0, r = nums.length - 1, ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] <= val) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans + 1; } // Counts elements >= val in a sorted array private int countGE(int[] nums, double val) { int l = 0, r = nums.length - 1, ans = nums.length; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] >= val) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return nums.length - ans; }}Complexity
Time
O(m * log(n) * log(Range)), where `m` and `n` are array lengths and `Range` is the difference between the maximum and minimum possible products (`~2*10^10`). We can optimize by ensuring `m <= n`, making it `O(min(m,n) * log(max(m,n)) * log(Range))`.
Space
O(1), as we are not storing any data structures that scale with the input size.
Trade-offs
Pros
Much more efficient than brute force in both time and space.
Avoids storing all products, leading to
O(1)space complexity.
Cons
The time complexity might still be too high for the tightest time limits, although it's a significant improvement over brute force.
This approach builds upon the binary search on the answer but optimizes the counting step. The countLessEqual(mid) function, which counts products less than or equal to a value mid, can be implemented in O(m+n) time instead of O(m log n). This is achieved by using a two-pointer technique that leverages the sorted nature of both arrays.
Algorithm
- The overall structure is the same as the previous binary search approach.
- The key improvement is in the
countLessEqual(mid)function, which is optimized to run inO(m+n)time. - To achieve this, we use a two-pointer technique. We iterate through
nums1from right to left. - We maintain two pointers for
nums2:p_posstarting at0andp_negstarting atn-1. - For each
x = nums1[i]:- If
x > 0: We needy <= mid / x. Asidecreases,xdecreases, somid / xincreases. The pointerp_poscan continue moving right from its last position to find the new boundary. We addp_posto the total count. - If
x < 0: We needy >= mid / x. Asidecreases,xbecomes more negative, somid / xincreases. The pointerp_negcan continue moving left from its last position. We addn - 1 - p_negto the total count. - If
x == 0: Ifmid >= 0, addnto the count.
- If
- Since both
p_posandp_negonly move in one direction throughout the iteration ofnums1, the total work for thecountLessEqualfunction isO(m+n).
Walkthrough
The core idea remains binary searching on the product's value. The optimization lies in the countLessEqual function. By exploiting the sorted property of both arrays, we can count the valid pairs in linear time.
We iterate through nums1 and use pointers on nums2. The direction of these pointers depends on the sign of the element from nums1. A clever way to ensure the pointers on nums2 move monotonically is to iterate nums1 from right to left.
- For
nums1[i] > 0, asidecreases,nums1[i]decreases. We neednums2[j] <= mid / nums1[i]. The right side of the inequality increases, so a pointerp_posonnums2can only move from left to right. - For
nums1[i] < 0, asidecreases,nums1[i]also decreases (becomes more negative). We neednums2[j] >= mid / nums1[i]. The right side of the inequality increases. A pointerp_negonnums2can only move from right to left.
This ensures that the pointers on nums2 don't reset, leading to an O(m+n) complexity for the counting function.
class Solution { public long kthSmallestProduct(int[] nums1, int[] nums2, long k) { long low = -10000000001L; long high = 10000000001L; long ans = high; while (low <= high) { long mid = low + (high - low) / 2; if (countLessEqual(nums1, nums2, mid) >= k) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } private long countLessEqual(int[] nums1, int[] nums2, long p) { long count = 0; int m = nums1.length; int n = nums2.length; int p_pos = 0; int p_neg = n - 1; for (int i = m - 1; i >= 0; i--) { int x = nums1[i]; if (x > 0) { while (p_pos < n && (long) x * nums2[p_pos] <= p) { p_pos++; } count += p_pos; } else if (x < 0) { while (p_neg >= 0 && (long) x * nums2[p_neg] <= p) { p_neg--; } count += (n - 1 - p_neg); } else { // x == 0 if (p >= 0) { count += n; } } } return count; }}Complexity
Time
O((m+n) * log(Range)). The binary search performs `log(Range)` iterations, and each call to the optimized `countLessEqual` function takes `O(m+n)` time.
Space
O(1), as no extra space proportional to the input size is used.
Trade-offs
Pros
The most efficient solution for this problem.
Optimal time complexity that passes all test cases.
Maintains
O(1)space complexity.
Cons
The logic for the
O(m+n)count function is complex to reason about and implement correctly, especially due to the presence of negative numbers which flips inequalities.
Solutions
Solution
class Solution {private int[] nums1;private int[] nums2;public long kthSmallestProduct(int[] nums1, int[] nums2, long k) { this.nums1 = nums1; this.nums2 = nums2; int m = nums1.length; int n = nums2.length; int a = Math.max(Math.abs(nums1[0]), Math.abs(nums1[m - 1])); int b = Math.max(Math.abs(nums2[0]), Math.abs(nums2[n - 1])); long r = (long)a * b; long l = (long)-a * b; while (l < r) { long mid = (l + r) >> 1; if (count(mid) >= k) { r = mid; } else { l = mid + 1; } } return l; }private long count(long p) { long cnt = 0; int n = nums2.length; for (int x : nums1) { if (x > 0) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if ((long)x * nums2[mid] > p) { r = mid; } else { l = mid + 1; } } cnt += l; } else if (x < 0) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if ((long)x * nums2[mid] <= p) { r = mid; } else { l = mid + 1; } } cnt += n - l; } else if (p >= 0) { cnt += n; } } return cnt; }}class Solution {public: long long kthSmallestProduct(vector<int> &nums1, vector<int> &nums2, long long k) { int m = nums1.size(), n = nums2.size(); int a = max(abs(nums1[0]), abs(nums1[m - 1])); int b = max(abs(nums2[0]), abs(nums2[n - 1])); long long r = 1LL * a * b; long long l = -r; auto count = [&](long long p) { long long cnt = 0; for (int x : nums1) { if (x > 0) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (1LL * x * nums2[mid] > p) { r = mid; } else { l = mid + 1; } } cnt += l; } else if (x < 0) { int l = 0, r = n; while (l < r) { int mid = (l + r) >> 1; if (1LL * x * nums2[mid] <= p) { r = mid; } else { l = mid + 1; } } cnt += n - l; } else if (p >= 0) { cnt += n; } } return cnt; }; while (l < r) { long long mid = (l + r) >> 1; if (count(mid) >= k) { r = mid; } else { l = mid + 1; } } return l; }};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) - mxVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.