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 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.
This solution uses a default dictionary initialized with base price 10. We iterate through the sorted list of products by product_id and date. For each product, if the change date is on or before the target date, we update the product's price in the dictionary. Finally, we prepare a list of results showing the product_id and its corresponding price on the given date.
JavaScript
Time Complexity: O(N log N), due to sorting the records.
Space Complexity: O(N), for storing the latest prices of the products.
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.
This C++ code uses STL map to mimic SQL grouping and filtering. It iterates over each record, checking change dates and storing the maximum price for each product that is valid for the date. The final step is to collect results by comparing stored prices against the base price.
C#
Time Complexity: O(N log N), primarily due to map operations.
Space Complexity: O(N), to store product_id and price mappings.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Group by Product ID and Change Date | Time Complexity: O(N log N), due to sorting the records. |
| Approach 2: Use SQL-like Logic to Handle Dates | Time Complexity: O(N log N), primarily due to map operations. |
LeetCode Medium 1164 Amazon Interview SQL Question with Detailed Explanation • Everyday Data Science • 8,574 views views
Watch 9 more video solutions →Practice Product Price at a Given Date with our built-in code editor and test cases.
Practice on FleetCode