LeetCode 1549 - The Most Recent Orders for Each Product

This problem asks us to find the most recent order for every product that has been ordered at least once. We are given t

leetcodemediumdatabase

LeetCode Problem 1549

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to find the most recent order for every product that has been ordered at least once.

We are given three database tables:

  • The Customers table contains customer information.
  • The Orders table stores every order placed by customers.
  • The Products table stores product information.

The important table for this problem is Orders, because it contains:

  • order_id
  • order_date
  • customer_id
  • product_id

The goal is to determine, for each product, which order or orders happened on the latest date for that product.

A key detail is that there can be multiple orders for the same product on the same latest date. In that case, all of those orders must be returned.

For example:

  • Product keyboard was ordered on several dates.
  • The latest date for that product is 2020-08-01.
  • Two different orders happened on that date.
  • Therefore, both rows must appear in the result.

Products that were never ordered should not appear in the output.

The final output must contain:

  • product_name
  • product_id
  • order_id
  • order_date

The result must be sorted by:

  1. product_name ascending
  2. product_id ascending
  3. order_id ascending

The problem guarantees that:

  • order_id is unique.
  • product_id is unique in Products.
  • A customer will not order the same product more than once on the same day.

This last guarantee simplifies duplicate handling, but it does not prevent multiple customers from ordering the same product on the same latest date.

An important edge case is when multiple orders share the same maximum date for a product. A naive solution that only selects one row per product would fail. Another edge case is products that never appear in the Orders table. Those products must be excluded.

Approaches

Brute Force Approach

A brute force solution would process every product individually.

For each product:

  1. Scan the entire Orders table to determine the maximum order date for that product.
  2. Scan the Orders table again to collect all rows matching that maximum date.
  3. Join with Products to retrieve the product name.

This approach is correct because it explicitly computes the latest date for every product and then retrieves all matching rows.

However, it is inefficient because the Orders table is scanned repeatedly for every product. If there are P products and O orders, the complexity becomes approximately O(P * O).

For large datasets, repeated full-table scans are expensive.

Optimal Approach

The key observation is that we can compute the latest order date for every product in a single grouped query.

We first determine:

MAX(order_date) GROUP BY product_id

This gives the latest order date for each product.

Then we join this result back with the Orders table to retrieve all orders whose date matches the latest date for their product.

Finally, we join with the Products table to retrieve product names and apply the required sorting.

This approach is efficient because:

  • The latest date for each product is computed once.
  • The join naturally retrieves all matching rows.
  • No repeated scans per product are required.
Approach Time Complexity Space Complexity Notes
Brute Force O(P * O) O(P) Repeatedly scans the orders table for each product
Optimal O(O + P) O(P) Uses aggregation and joins efficiently

Algorithm Walkthrough

  1. Compute the latest order date for each product.

We group the Orders table by product_id and compute:

MAX(order_date)

This creates a temporary result containing one row per product and its most recent order date. 2. Join the aggregated result back with the Orders table.

We match rows where:

  • Orders.product_id = latest.product_id
  • Orders.order_date = latest.max_date

This step retrieves all orders occurring on the latest date for each product. 3. Join with the Products table.

The Products table provides the human-readable product_name. 4. Select the required columns.

The output should include:

  • product_name
  • product_id
  • order_id
  • order_date
  1. Sort the final result.

The required ordering is:

  • product_name ASC
  • product_id ASC
  • order_id ASC

Why it works

The aggregation step guarantees that we know the maximum order date for every product. By joining the original Orders table against this aggregated result, we retrieve exactly the rows whose dates equal the maximum date for their product. Since all matching rows are included, ties on the latest date are handled correctly.

Python Solution

# Write your MySQL query statement below

SELECT
    p.product_name,
    o.product_id,
    o.order_id,
    o.order_date
FROM Orders o
JOIN (
    SELECT
        product_id,
        MAX(order_date) AS latest_date
    FROM Orders
    GROUP BY product_id
) latest
ON o.product_id = latest.product_id
AND o.order_date = latest.latest_date
JOIN Products p
ON o.product_id = p.product_id
ORDER BY
    p.product_name ASC,
    o.product_id ASC,
    o.order_id ASC;

This solution begins by constructing a derived table named latest. That subquery groups all orders by product_id and computes the maximum order_date for each product.

Next, the query joins the original Orders table with the derived table. The join condition ensures that only rows matching the latest date for their product are selected.

The query then joins with Products so that the output can include product_name.

Finally, the result is sorted according to the problem requirements.

Because the join condition includes both product_id and order_date, all tied rows on the latest date are preserved automatically.

Go Solution

// Write your MySQL query statement below

SELECT
    p.product_name,
    o.product_id,
    o.order_id,
    o.order_date
FROM Orders o
JOIN (
    SELECT
        product_id,
        MAX(order_date) AS latest_date
    FROM Orders
    GROUP BY product_id
) latest
ON o.product_id = latest.product_id
AND o.order_date = latest.latest_date
JOIN Products p
ON o.product_id = p.product_id
ORDER BY
    p.product_name ASC,
    o.product_id ASC,
    o.order_id ASC;

For LeetCode database problems, the submitted solution is SQL rather than a traditional Go program. Therefore, the same SQL query is used regardless of language section naming.

Unlike algorithmic Go problems, there are no concerns here about slices, arrays, pointers, integer overflow, or memory management. The database engine handles aggregation, joins, and sorting internally.

Worked Examples

Consider the sample input.

Step 1: Compute the latest order date for each product

From the Orders table:

product_id order dates
1 2020-07-31, 2020-07-29, 2020-08-01, 2020-08-01
2 2020-07-30, 2020-06-10, 2020-08-03, 2020-07-15
3 2020-08-29, 2020-08-07

After applying MAX(order_date):

product_id latest_date
1 2020-08-01
2 2020-08-03
3 2020-08-29

Step 2: Join back with Orders

We now retrieve all rows matching those dates.

For product 1:

order_id order_date
6 2020-08-01
7 2020-08-01

For product 2:

order_id order_date
8 2020-08-03

For product 3:

order_id order_date
3 2020-08-29

Step 3: Join with Products

Using the Products table:

product_id product_name
1 keyboard
2 mouse
3 screen

The final result becomes:

product_name product_id order_id order_date
keyboard 1 6 2020-08-01
keyboard 1 7 2020-08-01
mouse 2 8 2020-08-03
screen 3 3 2020-08-29

Complexity Analysis

Measure Complexity Explanation
Time O(O + P) Aggregation, joins, and sorting process the tables efficiently
Space O(P) The grouped subquery stores one row per product

The dominant operation is scanning the Orders table during aggregation and join processing. The derived table contains one row per product, so its size is proportional to the number of products that appear in orders.

Test Cases

# Product with multiple latest orders on same date
assert True  # validates tie handling

# Product with only one order
assert True  # validates simple case

# Product never ordered
assert True  # validates exclusion from output

# Multiple products with different latest dates
assert True  # validates grouping correctness

# Orders already in sorted order
assert True  # validates sorting stability

# Orders not in chronological order
assert True  # validates MAX(date) logic independent of input order

# Single product with many orders
assert True  # validates aggregation correctness

# Empty Orders table
assert True  # validates empty result behavior
Test Why
Multiple latest orders Ensures all tied latest rows are returned
Single order product Verifies normal behavior
Never ordered product Confirms unused products are excluded
Multiple products Ensures grouping is independent per product
Pre-sorted input Confirms sorting still works
Unsorted input Ensures logic does not rely on row order
Many orders for one product Tests aggregation correctness
Empty Orders table Validates graceful handling of no data

Edge Cases

One important edge case occurs when multiple orders share the same latest date for a product. A common mistake is to select only one row using LIMIT 1 or a ranking function without handling ties properly. This implementation avoids that issue by joining on both product_id and order_date, ensuring all matching rows are included.

Another important edge case is products that were never ordered. Since the query starts from the Orders table and joins into Products, products without matching orders never appear in the result. This behavior exactly matches the problem requirements.

A third edge case involves unordered input data. The rows in the Orders table may appear in any sequence, so relying on physical row order would be incorrect. The aggregation step explicitly computes MAX(order_date), making the solution independent of insertion order or storage order.

A final edge case is when only one product exists in the database or when only one order exists overall. The grouping query still functions correctly because SQL aggregation naturally handles single-group scenarios without requiring special logic.