Kth Smallest Product of Two Sorted Arrays
Hard
2 views
Topics:
ArraysBinary Search
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.
For example:
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.
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.
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.
Consider the edge cases such as:
- One or both arrays are empty.
- One or both arrays contain only negative numbers.
- One or both arrays contain only positive numbers.
kis equal to 1 ornums1.length * nums2.length.- Zeroes exist in one or both arrays.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the possible ranges and data types of the numbers within the two input arrays, and can they contain negative numbers, zeros, or floating-point values?
- What are the constraints on the size of the input arrays, and what value should I return if `k` is larger than the total number of possible products (i.e., product of the lengths of the two arrays)?
- Are the input arrays guaranteed to be sorted in ascending order, and are duplicate values allowed within the arrays?
- Is `k` 1-indexed or 0-indexed? In other words, does `k = 1` refer to the smallest product?
- If multiple pairs of elements result in the same kth smallest product, does the order in which they appear in the original arrays matter, or can I return any of those pairs?
Brute Force Solution
Approach
We want to find a particular product when we multiply numbers from two sorted lists together. The brute force way is to compute every possible product and then sort them.
Here's how the algorithm would work step-by-step:
- Take each number from the first list and multiply it by every number in the second list.
- Collect all of these products into a single big list.
- Sort this big list of products from smallest to largest.
- Find the product that is in the position we are looking for (the 'kth' position) in the sorted list. That's our answer!
Code Implementation
def kth_smallest_product_brute_force(first_array, second_array, k_value): all_products = []
# Iterate through all pairs to calculate products
for first_number in first_array:
for second_number in second_array:
all_products.append(first_number * second_number)
# Sorting is required to find the kth smallest element
all_products.sort()
# Return the kth smallest product
return all_products[k_value - 1]Big(O) Analysis
Time Complexity
O(n*m log(n*m)) – The algorithm iterates through each of the n elements of the first array and multiplies it with each of the m elements of the second array, generating n*m products. These products are then stored in a list. The sorting of this list containing n*m elements takes O(n*m log(n*m)) time. Therefore, the dominant operation is sorting the n*m products, resulting in a time complexity of O(n*m log(n*m)).
Space Complexity
O(N*M) – The brute force solution described first calculates all possible products between the two sorted arrays, storing these products in a single list. If the first array has N elements and the second array has M elements, this list will contain N*M product values. This list is auxiliary space, as it is not part of the original input. Sorting this list is typically done in place (e.g., using heapsort or quicksort in many standard libraries) but we are concerned with the auxiliary space *during* the construction of the products list. Thus, the auxiliary space complexity is O(N*M).
Optimal Solution
Approach
The problem asks us to find a specific product (the Kth smallest) from multiplying pairs of numbers taken from two sorted lists. We avoid checking every possible product directly. Instead, we use a technique that allows us to quickly narrow down the potential range where the Kth smallest product might lie, and then efficiently count how many products are smaller than a given value.
Here's how the algorithm would work step-by-step:
- First, figure out a good range for the possible products. The smallest and largest possible products from the lists will define this range.
- Use a process of educated guessing to find the target product. Pick a product value within the range.
- For this guessed product, efficiently count how many total products are smaller than it. Use the sorted nature of the lists to speed up this counting.
- Compare the count with 'K'. If the count is smaller than K, this means our guessed product is too small. If the count is greater than K, our guess is too big. Adjust our guess accordingly.
- Keep adjusting the guess (using something similar to the 'binary search' concept) and recalculating the count until we find the product that is just bigger than K-1 products. That product is our Kth smallest product.
Code Implementation
def kth_smallest_product(numbers_1, numbers_2, k_value):
def count_smaller_or_equal(product_value):
count = 0
for number_from_numbers_1 in numbers_1:
if number_from_numbers_1 >= 0:
left_index = 0
right_index = len(numbers_2) - 1
while left_index <= right_index:
middle_index = (left_index + right_index) // 2
if number_from_numbers_1 * numbers_2[middle_index] <= product_value:
left_index = middle_index + 1
else:
right_index = middle_index - 1
count += left_index
else:
left_index = 0
right_index = len(numbers_2) - 1
while left_index <= right_index:
middle_index = (left_index + right_index) // 2
if number_from_numbers_1 * numbers_2[middle_index] <= product_value:
right_index = middle_index - 1
else:
left_index = middle_index + 1
count += len(numbers_2) - left_index
return count
min_product = numbers_1[0] * numbers_2[0]
max_product = numbers_1[-1] * numbers_2[-1]
# Setting the range for binary search.
low_product = min(min_product, max_product)
high_product = max(min_product, max_product)
while low_product < high_product:
middle_product = low_product + (high_product - low_product) // 2
# Check how many products are less than middle_product
smaller_count = count_smaller_or_equal(middle_product)
# Adjust the range based on the count compared to k
if smaller_count < k_value:
low_product = middle_product + 1
else:
high_product = middle_product
# We've found the kth smallest product
return low_productBig(O) Analysis
Time Complexity
O(n log(max_product)) – The algorithm uses binary search to find the Kth smallest product within a range defined by the minimum and maximum possible products. The binary search continues until the Kth smallest product is found, taking O(log(max_product)) time, where max_product represents the difference between the largest and smallest possible product. Inside the binary search loop, we count the number of products less than or equal to the current guess. This counting involves iterating through one of the sorted arrays (of size n) and for each element performing a calculation and adjustment. The counting process within each binary search step takes O(n) time. Therefore, the overall time complexity is O(n log(max_product)).
Space Complexity
O(1) – The algorithm primarily uses a binary search approach. It only requires a few constant space variables to store the range boundaries, the middle value being guessed, and the count of products smaller than the guess. The counting process itself operates in place without creating additional data structures that scale with the input array sizes. Therefore, the auxiliary space remains constant regardless of the input size, leading to O(1) space complexity.
Edge Cases
| Case | How to Handle |
|---|---|
| One or both input arrays are empty | Return None or an appropriate error code as there are no products to consider. |
| One or both arrays contain only zero values | The Kth smallest product will be zero; handle the case where k is larger than the number of possible zero products. |
| Arrays contain both positive and negative numbers, including zeros | The algorithm needs to account for how negative numbers affect the ordering of products, potentially requiring a different approach to counting products less than or equal to a candidate value. |
| k is less than 1 or greater than the total number of possible products | Return None or raise an exception, as the Kth smallest product is not defined. |
| Integer overflow when calculating the product of two large numbers | Use a larger data type (e.g., long) or check for overflow before performing the multiplication. |
| Arrays with very large sizes, potentially causing performance issues during counting | Optimize the counting process by using binary search to find the number of elements satisfying the product condition. |
| All elements in both arrays are identical | Ensure that the binary search and counting logic correctly handle the many equal products. |
| k is very close to 1 or the maximum number of products, making binary search inefficient if initial bounds are far from the solution | Consider starting with a more informed initial range for binary search, possibly based on the smallest and largest possible products. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
