#1164 Product Price at a Given Date - Solution

Table: Products

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| product_id    | int     |
| new_price     | int     |
| change_date   | date    |
+---------------+---------+
(product_id, change_date) is the primary key (combination of columns with unique values) of this table.
Each row of this table indicates that the price of some product was changed to a new price at some date.

Write a solution to find the prices of all products on 2019-08-16. Assume the price of all products before any change is 10.

Return the result table in any order.

The result format is in the following example.

Example 1:

Input: 
Products table:
+------------+-----------+-------------+
| 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  |
+------------+-----------+-------------+
Output: 
+------------+-------+
| product_id | price |
+------------+-------+
| 2          | 50    |
| 1          | 35    |
| 3          | 10    |
+------------+-------+

In #1164 Product Price at a Given Date, the goal is to determine the price of every product on a specific date based on historical price updates. Each row in the table records a new price with the date it became effective. If a product has no price change before the given date, its price defaults to 10.

The key idea is to retrieve the most recent price change that occurred on or before the target date for each product. This can be done using a subquery that finds MAX(change_date) per product_id where the date is less than or equal to the target. The result can then be joined back to the table to obtain the corresponding price. Another clean approach uses window functions such as ROW_NUMBER() partitioned by product_id and ordered by change_date DESC to select the latest valid record.

Finally, handle products without earlier updates using COALESCE or conditional logic to return the default price. The approach efficiently filters historical records while keeping the query readable.

Approach	Time Complexity	Space Complexity
Subquery with MAX(change_date) and JOIN	O(n log n) depending on indexing and grouping	O(n)
Window Function (ROW_NUMBER partitioned by product)	O(n log n) due to sorting within partitions	O(n)

Solutions (4)

Approach 1: Sort and Group by Product ID and Change Date

In this approach, we can utilize sorting and grouping to find the last change before or on the specified date. We'll sort the input by product_id and change_date thus facilitating checking the last change on or before 2019-08-16. If no change is present by that date, we assign a default price of 10 for those products.

Time Complexity: O(N log N), due to sorting the records.
Space Complexity: O(N), for storing the latest prices of the products.

Python JavaScript

1function productPricesOnDate(products) {
2    const basePrice = 10;
3    const targetDate = '2019-08-16';
4    const productLatest = {};
5
6    products.sort((a, b) => {
7        if (a[0] === b[0]) {
8            return new Date(a[2]) - new Date(b[2]);
9        }
10        return a[0] - b[0];
11    });
12
13    for (const [product_id, new_price, change_date] of products) {
14        if (change_date <= targetDate) {
15            productLatest[product_id] = new_price;
16        }
17    }
18
19    return Object.entries(productLatest).map(([product_id, price]) => ({
20        product_id: parseInt(product_id, 10),
21        price: price || basePrice,
22    }));
23}

Explanation

This JavaScript function follows the same logic as the Python solution. We sort the products first and update a dictionary with the latest price for each product on or before the target date, using a base price if no such price is found. We then map through this dictionary to structure the result.

Approach 2: Use SQL-like Logic to Handle Dates

This approach simulates SQL operations in code logic to find the latest price for a given product_id on or before 2019-08-16. This can be done by first grouping by product_id and filtering with a date condition.

Time Complexity: O(N log N), primarily due to map operations.
Space Complexity: O(N), to store product_id and price mappings.

C++C#

1#include <iostream>
2#include <vector>
3#include <map>
4#include <tuple>
5#include <string>
#include <algorithm>

using namespace std;

vector<pair<int, int>> productPricesOnDate(vector<tuple<int, int, string>> &products) {
    int basePrice = 10;
    string targetDate = "2019-08-16";
    map<int, int> productLatestPrice;
    
    for (const auto &[product_id, new_price, change_date] : products) {
        if (change_date <= targetDate) {
            productLatestPrice[product_id] = max(productLatestPrice[product_id], new_price);
        }
    }

    vector<pair<int, int>> result;
    for (const auto &[product_id, price]: productLatestPrice) {
        result.emplace_back(product_id, (price != 0) ? price : basePrice);
    }
    
    return result;
}