LeetCode 1164 - Product Price at a Given Date

The problem provides a database table named Products, where each row represents a price update for a product on a specific date.

leetcodemediumdatabase

LeetCode Problem 1164

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem provides a database table named Products, where each row represents a price update for a product on a specific date. The columns are:

Column Meaning
product_id The identifier of the product
new_price The new price assigned to the product
change_date The date when the new price became effective

The pair (product_id, change_date) is guaranteed to be unique, meaning a product can have at most one price update per day.

Initially, before any updates occur, every product has a default price of 10.

The goal is to determine the price of every product on the date 2019-08-16.

This means that for each product:

  • If the product had one or more price changes on or before 2019-08-16, we must use the most recent such change.
  • If the product had no price changes before or on 2019-08-16, then its price remains the initial value of 10.

The output should contain every product that appears anywhere in the table, along with its effective price on 2019-08-16.

The important detail is that we are not looking for the latest price overall. We only care about the latest price up to the target date. Any changes after 2019-08-16 must be ignored.

Several edge cases are important:

  • A product may only have updates after 2019-08-16. In that case, its price should still be 10.
  • A product may have multiple updates before the target date. We must choose the most recent one.
  • A product may have an update exactly on 2019-08-16, which should be included.
  • Different products may have completely different update histories.

This is fundamentally a "latest record before a cutoff date" database query problem.

Approaches

Brute Force Approach

A straightforward approach is to process each product independently.

For every distinct product_id, we can scan all rows belonging to that product and identify the latest change_date that is less than or equal to 2019-08-16. Once found, we return the corresponding new_price. If no such row exists, we return 10.

This works because it explicitly checks every possible price change and directly applies the problem definition.

However, this approach becomes inefficient because each product may require scanning many rows repeatedly. If there are n rows and m distinct products, the worst-case complexity can approach O(m * n).

In a large dataset, repeatedly rescanning the table is unnecessarily expensive.

Optimal Approach

The key observation is that we only need the most recent price update before or on 2019-08-16 for each product.

This naturally suggests grouping rows by product and selecting the maximum valid change_date.

The optimal SQL solution uses:

  • A subquery to compute the latest valid change_date for each product
  • A join back to the original table to retrieve the associated new_price
  • A fallback value of 10 for products without any qualifying updates

This avoids repeated scans and leverages SQL aggregation efficiently.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(1) Scan rows repeatedly for each product
Optimal O(n) O(n) Uses grouping and joins to efficiently locate latest valid prices

Algorithm Walkthrough

  1. First, identify all distinct products present in the table.

This is necessary because every product must appear in the final output, even if it never had a qualifying price update before 2019-08-16. 2. Find the latest valid price update for each product.

We filter rows where change_date <= '2019-08-16'.

Then, for each product, we compute the maximum change_date.

This gives us the most recent applicable update for every product that had at least one valid change before or on the target date. 3. Join the result back to the original table.

The aggregation step only gives us the date. We still need the corresponding new_price.

By joining on both:

  • product_id
  • change_date

we retrieve the exact row containing the effective price. 4. Handle products with no qualifying updates.

Some products may only have updates after 2019-08-16.

These products will not appear in the aggregation result.

For such cases, we use the default initial price of 10. 5. Return the final (product_id, price) pairs.

The problem allows the rows to be returned in any order.

Why it works

The algorithm relies on a simple invariant:

For each product, the correct price on a date is determined by the latest price update that occurred on or before that date.

By explicitly selecting the maximum valid change_date, we guarantee that no later applicable update exists. Joining back to retrieve the corresponding price ensures we return the exact effective value.

Products with no qualifying updates correctly retain the initial default price of 10.

Python Solution

class Solution:
    def productPrices(self, products: List[List]):
        import pandas as pd

        products_df = pd.DataFrame(
            products,
            columns=["product_id", "new_price", "change_date"]
        )

        target_date = "2019-08-16"

        latest_changes = (
            products_df[products_df["change_date"] <= target_date]
            .groupby("product_id")["change_date"]
            .max()
            .reset_index()
        )

        latest_prices = latest_changes.merge(
            products_df,
            on=["product_id", "change_date"],
            how="left"
        )[["product_id", "new_price"]]

        latest_prices.rename(columns={"new_price": "price"}, inplace=True)

        all_products = products_df[["product_id"]].drop_duplicates()

        result = all_products.merge(
            latest_prices,
            on="product_id",
            how="left"
        )

        result["price"] = result["price"].fillna(10).astype(int)

        return result

The solution begins by converting the input into a pandas DataFrame so that grouping and joining operations become straightforward.

Next, the code filters rows whose change_date is less than or equal to the target date. This removes irrelevant future price updates.

The groupby(...).max() operation computes the latest valid date for each product. At this point, we know exactly which update should determine the product's price.

The merge operation reconnects those dates with their corresponding new_price values.

After renaming new_price to price, the solution constructs a list of all distinct products. This is important because products without qualifying updates still need to appear in the result.

Finally, a left join combines all products with the computed prices. Missing values are replaced with 10, which represents the default initial price.

Go Solution

func productPrices(products [][]interface{}) *DataFrame {
	type ProductRecord struct {
		ProductID int
		NewPrice  int
		ChangeDate string
	}

	records := []ProductRecord{}

	for _, row := range products {
		record := ProductRecord{
			ProductID: row[0].(int),
			NewPrice: row[1].(int),
			ChangeDate: row[2].(string),
		}
		records = append(records, record)
	}

	targetDate := "2019-08-16"

	latestDate := make(map[int]string)

	for _, record := range records {
		if record.ChangeDate <= targetDate {
			if current, exists := latestDate[record.ProductID]; !exists || record.ChangeDate > current {
				latestDate[record.ProductID] = record.ChangeDate
			}
		}
	}

	priceMap := make(map[int]int)

	for _, record := range records {
		if latest, exists := latestDate[record.ProductID]; exists &&
			record.ChangeDate == latest {
			priceMap[record.ProductID] = record.NewPrice
		}
	}

	allProducts := make(map[int]bool)

	for _, record := range records {
		allProducts[record.ProductID] = true
	}

	result := []map[string]interface{}{}

	for productID := range allProducts {
		price := 10

		if value, exists := priceMap[productID]; exists {
			price = value
		}

		result = append(result, map[string]interface{}{
			"product_id": productID,
			"price":      price,
		})
	}

	return CreateDataFrame(result)
}

The Go implementation follows the same logical structure as the Python version but uses explicit maps instead of DataFrame operations.

The latestDate map stores the most recent valid update date for each product.

The priceMap map stores the corresponding effective price.

Finally, every distinct product is added to the output, defaulting to 10 if no valid update exists.

Since date strings are in YYYY-MM-DD format, lexicographical string comparison works correctly for chronological ordering.

Worked Examples

Example 1

Input:

product_id new_price change_date
1 20 2019-08-14
2 50 2019-08-14
1 30 2019-08-15
1 35 2019-08-16
2 65 2019-08-17
3 20 2019-08-18

Target date:

2019-08-16

Step 1: Filter valid rows

Keep only rows where change_date <= 2019-08-16.

product_id new_price change_date
1 20 2019-08-14
2 50 2019-08-14
1 30 2019-08-15
1 35 2019-08-16

Rows after the target date are ignored.

Step 2: Find latest valid date per product

product_id latest_date
1 2019-08-16
2 2019-08-14

Product 3 does not appear because it has no qualifying updates.

Step 3: Retrieve corresponding prices

product_id price
1 35
2 50

Step 4: Add missing products with default price

Product 3 never changed before the target date, so its price remains 10.

Final result:

product_id price
1 35
2 50
3 10

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed a constant number of times
Space O(n) Additional storage for grouped results and mappings

The solution performs filtering, grouping, and joining operations that each scale linearly with the number of rows in the table.

The auxiliary storage is proportional to the number of distinct products and intermediate grouped results.

Test Cases

def compute_prices(products):
    from collections import defaultdict

    latest = {}

    for product_id, new_price, change_date in products:
        if change_date <= "2019-08-16":
            if (
                product_id not in latest or
                change_date > latest[product_id][0]
            ):
                latest[product_id] = (change_date, new_price)

    result = {}

    for product_id, _, _ in products:
        result[product_id] = 10

    for product_id, (_, price) in latest.items():
        result[product_id] = price

    return result

# Provided example
assert compute_prices([
    [1, 20, "2019-08-14"],
    [2, 50, "2019-08-14"],
    [1, 30, "2019-08-15"],
    [1, 35, "2019-08-16"],
    [2, 65, "2019-08-17"],
    [3, 20, "2019-08-18"]
]) == {
    1: 35,
    2: 50,
    3: 10
}  # Standard mixed updates

# Product updated exactly on target date
assert compute_prices([
    [1, 99, "2019-08-16"]
]) == {
    1: 99
}  # Exact cutoff inclusion

# Product only updated after target date
assert compute_prices([
    [1, 50, "2019-08-20"]
]) == {
    1: 10
}  # Uses default price

# Multiple updates before target date
assert compute_prices([
    [1, 10, "2019-08-10"],
    [1, 20, "2019-08-11"],
    [1, 30, "2019-08-12"]
]) == {
    1: 30
}  # Latest valid update wins

# Multiple products with mixed histories
assert compute_prices([
    [1, 15, "2019-08-10"],
    [2, 25, "2019-08-17"],
    [3, 35, "2019-08-15"]
]) == {
    1: 15,
    2: 10,
    3: 35
}  # Combination of valid and invalid updates

# Single product with many updates
assert compute_prices([
    [1, 5, "2019-08-01"],
    [1, 15, "2019-08-05"],
    [1, 25, "2019-08-10"],
    [1, 35, "2019-08-16"],
    [1, 45, "2019-08-20"]
]) == {
    1: 35
}  # Ignore future updates
Test Why
Provided example Validates standard mixed behavior
Update exactly on target date Ensures inclusive comparison
Only future updates Confirms default price handling
Multiple prior updates Verifies latest valid update selection
Mixed product histories Ensures products are handled independently
Many updates for one product Confirms future rows are ignored

Edge Cases

One important edge case occurs when a product only has updates after the target date. A naive implementation might accidentally exclude the product entirely because no valid updates exist before the cutoff. The correct behavior is to return the default price of 10. The implementation handles this by first collecting all distinct products and later filling missing prices with 10.

Another important edge case is when a product has multiple updates before the target date. The algorithm must select the most recent valid update, not the first one encountered. This is why the grouping step uses the maximum change_date for each product.

A third important edge case is when a product changes price exactly on 2019-08-16. The problem explicitly asks for prices on that date, so updates occurring that day must be included. The implementation uses <= '2019-08-16' rather than < '2019-08-16', ensuring the cutoff date itself is considered valid.

A final subtle edge case involves products with both earlier and later updates. The algorithm must ignore all future changes even if they are the latest overall. By filtering rows before grouping, the implementation guarantees that only historically valid updates influence the result.