LeetCode 3293 - Calculate Product Final Price

The problem asks us to calculate the final price for each product in a database, taking into account any category-specific discounts. We are given two tables: Products and Discounts. The Products table contains each product's unique ID, its category, and its original price.

leetcodemediumdatabase

LeetCode Problem 3293

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to calculate the final price for each product in a database, taking into account any category-specific discounts. We are given two tables: Products and Discounts. The Products table contains each product's unique ID, its category, and its original price. The Discounts table contains a discount percentage for each category. Our goal is to produce a result table that lists each product's ID, its final price after applying the discount (if any), and its category. If a product's category does not have a discount listed, the final price should remain the same as the original price. The results must be ordered by product_id in ascending order.

Key points include that discounts are percentages, so the final price is calculated as price - (price * discount / 100). We must handle cases where some categories have no discount. The problem guarantees that product_id is unique and that category names are consistent between tables.

Important edge cases include products with categories that do not exist in the Discounts table, products with zero price, and discounts of 0% or 100%. We must ensure that calculations do not produce null or incorrect values in these cases.

Approaches

The brute-force approach would involve iterating over each product and searching the entire Discounts table to find a matching category. This guarantees the correct answer but is inefficient, as each lookup could take O(n) time for a total of O(m*n), where m is the number of products and n is the number of discounts.

The optimal approach uses a hash-based lookup or a SQL join. By joining the Products table with the Discounts table on the category column, we can directly access the discount for each product. For products with no matching discount, we use a default value of 0. This approach is efficient because the database engine can handle the join operation optimally, or in code we can precompute a dictionary for constant-time lookup.

Approach Time Complexity Space Complexity Notes
Brute Force O(m*n) O(1) For each product, iterate through all discounts to find the match.
Optimal O(m + n) O(n) Build a dictionary for discounts and iterate over products once, applying the discount.

Algorithm Walkthrough

  1. Create a hash map (dictionary) that maps each category in the Discounts table to its corresponding discount percentage. This allows O(1) lookup for any product's category.
  2. Iterate over each product in the Products table.
  3. For each product, check if its category exists in the discount map.
  4. If a discount exists, calculate the final price as price - (price * discount / 100).
  5. If no discount exists, retain the original price as the final price.
  6. Store the result in a list or table with product_id, final_price, and category.
  7. Sort the final result by product_id in ascending order before returning.

Why it works: By precomputing the discount map, we ensure that every product has constant-time access to its discount if it exists. This guarantees correctness and efficiency, and sorting by product_id ensures the required output order.

Python Solution

import pandas as pd

def calculate_final_price(products: pd.DataFrame, discounts: pd.DataFrame) -> pd.DataFrame:
    # Create a discount dictionary for O(1) lookups
    discount_map = dict(zip(discounts['category'], discounts['discount']))
    
    # Apply discount to each product
    def apply_discount(row):
        discount = discount_map.get(row['category'], 0)
        final_price = row['price'] * (1 - discount / 100)
        return final_price
    
    products['final_price'] = products.apply(apply_discount, axis=1)
    
    # Select and reorder columns
    result = products[['product_id', 'final_price', 'category']]
    
    # Sort by product_id
    result = result.sort_values(by='product_id').reset_index(drop=True)
    
    return result

In this implementation, we first build a dictionary for discounts, which allows fast lookup. The apply_discount function handles both products with and without discounts. Finally, we sort the result by product_id to meet the output requirements.

Go Solution

package main

import (
	"fmt"
	"sort"
)

type Product struct {
	ProductID int
	Category  string
	Price     float64
}

type Discount struct {
	Category string
	Discount int
}

type Result struct {
	ProductID  int
	FinalPrice float64
	Category   string
}

func CalculateFinalPrice(products []Product, discounts []Discount) []Result {
	// Build discount map
	discountMap := make(map[string]int)
	for _, d := range discounts {
		discountMap[d.Category] = d.Discount
	}

	// Compute final prices
	results := make([]Result, 0, len(products))
	for _, p := range products {
		disc := discountMap[p.Category]
		finalPrice := p.Price * (1 - float64(disc)/100)
		results = append(results, Result{p.ProductID, finalPrice, p.Category})
	}

	// Sort by ProductID
	sort.Slice(results, func(i, j int) bool {
		return results[i].ProductID < results[j].ProductID
	})

	return results
}

In Go, we explicitly handle the mapping from category to discount with a map. The final prices are calculated similarly, and sorting uses Go's sort.Slice function.

Worked Examples

For the provided example:

Step 1: Build the discount map

Category Discount
Electronics 10
Clothing 20

Step 2: Process each product

ProductID Category Price Discount Final Price
1 Electronics 1000 10 900
2 Clothing 50 20 40
3 Electronics 1200 10 1080
4 Home 500 0 500

Step 3: Sort by product_id (already sorted).

Complexity Analysis

Measure Complexity Explanation
Time O(m + n) Build discount map in O(n) and iterate over products in O(m).
Space O(n) Store discount map with n entries.

The algorithm is efficient because each product is processed once and lookup in the discount map is O(1).

Test Cases

# Provided example
assert calculate_final_price(
    pd.DataFrame({
        'product_id': [1, 2, 3, 4],
        'category': ['Electronics', 'Clothing', 'Electronics', 'Home'],
        'price': [1000, 50, 1200, 500]
    }),
    pd.DataFrame({
        'category': ['Electronics', 'Clothing'],
        'discount': [10, 20]
    })
).equals(pd.DataFrame({
    'product_id': [1, 2, 3, 4],
    'final_price': [900, 40, 1080, 500],
    'category': ['Electronics', 'Clothing', 'Electronics', 'Home']
}))

# Edge case: No discounts
assert calculate_final_price(
    pd.DataFrame({'product_id':[1], 'category':['Books'], 'price':[100]}),
    pd.DataFrame({'category':[], 'discount':[]})
).iloc[0]['final_price'] == 100

# Edge case: Discount 100%
assert calculate_final_price(
    pd.DataFrame({'product_id':[1], 'category':['Clearance'], 'price':[200]}),
    pd.DataFrame({'category':['Clearance'], 'discount':[100]})
).iloc[0]['final_price'] == 0

# Edge case: Price 0
assert calculate_final_price(
    pd.DataFrame({'product_id':[1], 'category':['Freebies'], 'price':[0]}),
    pd.DataFrame({'category':['Freebies'], 'discount':[50]})
).iloc[0]['final_price'] == 0
Test Why
Provided example Validates normal discount application and no-discount cases
No discounts Ensures products with no discount remain unchanged
Discount 100% Tests full discount edge case
Price 0 Tests zero price edge case

Edge Cases

The first edge case is a product belonging to a category not present in the Discounts table. This tests that the algorithm correctly defaults to a zero discount and does not produce null or incorrect final prices. The second edge case is a 100% discount, which ensures that the algorithm correctly computes a final price of zero. The third edge case is a product with zero price, which tests that applying any discount does not result in negative prices or errors. Each of these cases is handled naturally by the discount lookup logic and the arithmetic formula.