Problem

Table: Products

1
2
3
4
5
6
7
8
9

+---------------+---------+
| 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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    |
+------------+-------+

Solution

Method 1 – Find Latest Price Before or On Date

Intuition

We need to find the price of each product as of a specific date. For each product, find the latest price change on or before the given date; if none, the price is 10.

Approach

  1. For each product, find the latest change_date on or before ‘2019-08-16’.
  2. If there is a price change, use that price; otherwise, use 10.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

SELECT p.product_id, COALESCE(t.new_price, 10) AS price
FROM (SELECT DISTINCT product_id FROM Products) p
LEFT JOIN (
    SELECT product_id, new_price
    FROM Products
    WHERE (product_id, change_date) IN (
        SELECT product_id, MAX(change_date)
        FROM Products
        WHERE change_date <= '2019-08-16'
        GROUP BY product_id
    )
) t ON p.product_id = t.product_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

SELECT p.product_id, COALESCE(t.new_price, 10) AS price
FROM (SELECT DISTINCT product_id FROM Products) p
LEFT JOIN (
    SELECT product_id, new_price
    FROM Products
    WHERE (product_id, change_date) IN (
        SELECT product_id, MAX(change_date)
        FROM Products
        WHERE change_date <= '2019-08-16'
        GROUP BY product_id
    )
) t ON p.product_id = t.product_id;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# Assume Products is a pandas DataFrame
import pandas as pd
def product_price_at_given_date(Products: pd.DataFrame) -> pd.DataFrame:
    Products = Products.copy()
    Products['change_date'] = pd.to_datetime(Products['change_date'])
    asof_date = pd.to_datetime('2019-08-16')
    # Find latest change on or before the date
    mask = Products['change_date'] <= asof_date
    latest = Products[mask].sort_values(['product_id', 'change_date']).groupby('product_id').last().reset_index()
    all_ids = Products[['product_id']].drop_duplicates()
    result = all_ids.merge(latest[['product_id', 'new_price']], on='product_id', how='left')
    result['price'] = result['new_price'].fillna(10).astype(int)
    return result[['product_id', 'price']]

Complexity

  • ⏰ Time complexity: O(N) where N is the number of rows in Products.
  • 🧺 Space complexity: O(P) where P is the number of products.