Bigbasket's Optimal Product Pairing for Deals
Bigbasket frequently creates special deals by pairing two complementary products together. To efficiently identify potential deals, they need a system to find all product pairs that fall within a desired total price range. This capability helps in dynamically adjusting promotions, creating curated bundles, and highlighting valuable combinations to customers, ultimately enhancing sales and customer satisfaction.
Given a list of available products, a minimum total price, and a maximum total price, your task is to implement a function that finds all unique pairs of distinct products whose combined price falls within the specified range (inclusive).
Your solution must satisfy the following conditions:
(product_A, product_B) where product_A and product_B are distinct products from the input list.product_A.price + product_B.price, must be greater than or equal to minTotalPrice and less than or equal to maxTotalPrice.[id1, id2]. To ensure uniqueness and consistent representation, id1 must always be less than id2 within a pair.product_A.price + product_B.price) in ascending order.id1 (the first ID in the pair) in ascending order.id1 are equal, sort by id2 (the second ID in the pair) in ascending order.Input:
products: An array of objects. Each object represents a product and has the following structure:
interface Product {
id: number; // A unique identifier for the product
price: number; // The price of the product
}
minTotalPrice: A number representing the minimum acceptable combined price for a pair.maxTotalPrice: A number representing the maximum acceptable combined price for a pair.Output:
number[][] (array of arrays of numbers). Each inner array [id1, id2] represents a valid pair of product IDs, sorted as specified in the 'What you need to do / Task' section.products array will contain objects with unique id values.[].Examples
Example 1
Input:
products = [{id: 1, price: 10}, {id: 2, price: 20}, {id: 3, price: 30}, {id: 4, price: 40}], minTotalPrice = 30, maxTotalPrice = 50
Output:
[[1,2],[1,3],[1,4],[2,3]]
Note:
Sorted products by price: [{id: 1, price: 10}, {id: 2, price: 20}, {id: 3, price: 30}, {id: 4, price: 40}]. Valid pairs and their sums:
Raw pairs: [[1,2], [1,3], [1,4], [2,3]] Sorting by sum (asc), then id1 (asc), then id2 (asc):
Example 2
Input:
products = [{id: 10, price: 5}, {id: 20, price: 8}, {id: 30, price: 12}], minTotalPrice = 20, maxTotalPrice = 25
Output:
[]
Note:
Sorted products by price: [{id: 10, price: 5}, {id: 20, price: 8}, {id: 30, price: 12}]. Possible pairs and their sums:
However, the problem requires minTotalPrice = 20 and maxTotalPrice = 25. Only (20,30) sums to 20, which is within the range. But I made a mistake in the example, the sum of (20,30) is 20, which is valid. Let's correct the explanation. No, sum 20 is valid. I should ensure the output is correct. Let's make an example where NO pairs are found.
Corrected Example 2:
products = [{id: 10, price: 5}, {id: 20, price: 8}, {id: 30, price: 12}], minTotalPrice = 21, maxTotalPrice = 25
Only pair (20,30) has sum 20, which is outside [21,25]. Thus, no pairs.
Example 3
Input:
products = [{id: 100, price: 500000000}, {id: 200, price: 600000000}, {id: 300, price: 700000000}], minTotalPrice = 1000000000, maxTotalPrice = 1200000000
Output:
[[100,200],[100,300]]
Note:
Sorted products by price: [{id: 100, price: 5e8}, {id: 200, price: 6e8}, {id: 300, price: 7e8}]
Valid pairs and their sums:
Result after sorting: [[100,200], [100,300]]
Constraints
1 <= products.length <= 20001 <= products[i].id <= 10^91 <= products[i].price <= 10^91 <= minTotalPrice <= maxTotalPrice <= 2 * 10^9ids in the input array are unique.minTotalPrice/maxTotalPrice values.Loading editor...