How do you solve Average Selling Price on LeetCode?

Average Selling Price (LeetCode #1251) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding how to map prices to sales dates is crucial.

What is the brute force solution for Average Selling Price?

The brute force approach for Average Selling Price is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will iterate through each product's sales and calculate the total revenue and total units sold. This method is straightforward but inefficient for larger datasets. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Average Selling Price?

Average Selling Price uses the following concepts: Database. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Average Selling Price?

Explain your thought process clearly while coding. Ask clarifying questions about the problem constraints. Test your solution with different inputs to ensure accuracy.

What are common mistakes when solving Average Selling Price?

Not considering edge cases where no units are sold. Overlooking the need to round the average price correctly.

#1251

Average Selling Price

Easy

DatabaseHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal solution, we will use a single pass through the UnitsSold table while leveraging a HashMap to store prices, allowing us to calculate the average price efficiently.

⚙️

Algorithm

6 steps

1Step 1: Create a HashMap to store the price of each product based on its valid date range.
2Step 2: Iterate through the Prices table and populate the HashMap with product_id as the key and a tuple of (price, start_date, end_date) as the value.
3Step 3: Initialize another HashMap to track total revenue and total units sold for each product_id.
4Step 4: Iterate through the UnitsSold table, and for each sale, use the HashMap to find the price for that product_id based on the purchase_date.
5Step 5: Update total revenue and total units sold in the second HashMap.
6Step 6: Calculate the average price for each product_id and prepare the result.

solution.py24 lines

1# Full working Python code
2import pandas as pd
3
4def average_selling_price(prices, units_sold):
5    price_map = {}
6    for _, row in prices.iterrows():
7        price_map[row['product_id']] = (row['price'], row['start_date'], row['end_date'])
8
9    revenue_map = {}
10    units_map = {}
11    for _, sale in units_sold.iterrows():
12        product_id = sale['product_id']
13        purchase_date = sale['purchase_date']
14        if product_id in price_map:
15            price, start_date, end_date = price_map[product_id]
16            if start_date <= purchase_date <= end_date:
17                revenue_map[product_id] = revenue_map.get(product_id, 0) + price * sale['units']
18                units_map[product_id] = units_map.get(product_id, 0) + sale['units']
19
20    result = []
21    for product_id in set(revenue_map.keys()).union(units_map.keys()):
22        average_price = round(revenue_map.get(product_id, 0) / units_map.get(product_id, 1), 2)
23        result.append({'product_id': product_id, 'average_price': average_price})
24    return pd.DataFrame(result)

ℹ

Complexity note: The time complexity is O(n) because we only iterate through the UnitsSold and Prices tables once each, making it efficient for large datasets.

1Understanding how to map prices to sales dates is crucial.
2Efficient data retrieval can significantly reduce computation time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.