Frontend School

Bigbasket's Optimal Product Pairing for Deals

DSA
medium

Bigbasket's Optimal Product Pairing for Deals

Medium
Sorting
Two Pointers
Arrays

Overview

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.

What you need to do / Task

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:

  1. Identify all pairs (product_A, product_B) where product_A and product_B are distinct products from the input list.
  2. The sum of their prices, product_A.price + product_B.price, must be greater than or equal to minTotalPrice and less than or equal to maxTotalPrice.
  3. Each returned pair should be represented as an array of two product IDs [id1, id2]. To ensure uniqueness and consistent representation, id1 must always be less than id2 within a pair.
  4. The final list of pairs must be sorted according to these criteria:
    • Primary sort: By the total price of the pair (sum of product_A.price + product_B.price) in ascending order.
    • Secondary sort: If total prices are equal, sort by id1 (the first ID in the pair) in ascending order.
    • Tertiary sort: If both total prices and id1 are equal, sort by id2 (the second ID in the pair) in ascending order.

Input & Output

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:

  • A 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.

Clarifications

  • A product cannot be paired with itself.
  • The input products array will contain objects with unique id values.
  • If no pairs satisfy the conditions, return an empty array [].

Examples

1

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:

  • (1, 2): sum = 30 (valid)
  • (1, 3): sum = 40 (valid)
  • (1, 4): sum = 50 (valid)
  • (2, 3): sum = 50 (valid)
  • (2, 4): sum = 60 (invalid, > 50). The inner loop breaks here for product 2.
  • (3, 4): sum = 70 (invalid, > 50). The inner loop breaks here for product 3.

Raw pairs: [[1,2], [1,3], [1,4], [2,3]] Sorting by sum (asc), then id1 (asc), then id2 (asc):

  • [1,2] (sum 30)
  • [1,3] (sum 40)
  • [1,4] (sum 50, id1 1)
  • [2,3] (sum 50, id1 2) Result: [[1,2],[1,3],[1,4],[2,3]]
2

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:

  • (10, 20): sum = 13
  • (10, 30): sum = 17
  • (20, 30): sum = 20 (valid)

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.

3

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:

  • (100, 200): sum = 1.1e9 (valid, within [1e9, 1.2e9])
  • (100, 300): sum = 1.2e9 (valid, within [1e9, 1.2e9])
  • (200, 300): sum = 1.3e9 (invalid, > 1.2e9). The inner loop breaks here for product 200.

Result after sorting: [[100,200], [100,300]]

Constraints

Constraints & assumptions

  • 1 <= products.length <= 2000
  • 1 <= products[i].id <= 10^9
  • 1 <= products[i].price <= 10^9
  • 1 <= minTotalPrice <= maxTotalPrice <= 2 * 10^9
  • All product ids in the input array are unique.
  • Prices are positive integers.

What interviewers evaluate

  • Correctness: The solution correctly identifies all valid pairs and adheres to all sorting requirements.
  • Efficiency: The algorithm demonstrates an optimal or near-optimal time complexity for the given constraints.
  • Clarity and Readability: The code is well-structured, easy to understand, and follows good coding practices.
  • Edge Cases: The solution gracefully handles edge cases such as empty results or boundary minTotalPrice/maxTotalPrice values.

Loading editor...