LeetCode 1532 - The Most Recent Three Orders

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to retrieve the three most recent orders for every customer from a database. If a customer has fewer than three orders, we should return all of their orders.

We are given two tables:

The Customers table contains customer information. Each customer has a unique customer_id and a corresponding name.

The Orders table stores customer purchases. Each order has a unique order_id, an order_date, the customer_id who placed it, and a cost. The problem guarantees that each customer has at most one order per day, which simplifies ordering because there are no duplicate dates per customer.

The goal is to return a result table containing:

customer_name
customer_id
order_id
order_date

However, we only include the most recent three orders per customer.

The output must follow a strict sorting rule:

Sort by customer_name in ascending order.
If names tie, sort by customer_id in ascending order.
If there is still a tie, sort by order_date in descending order.

The key challenge is that we are not simply sorting the entire table. We must first determine the top three most recent orders within each customer group.

This is a classic group-wise top K problem, where we need to rank rows independently for each customer and keep only the highest-ranked ones.

An important observation is that SQL databases are designed for this kind of grouped ranking through window functions, particularly ROW_NUMBER().

Some important edge cases are worth identifying early:

A customer may have fewer than three orders, in which case all orders must be returned.
A customer may have exactly three orders, in which case every order is returned.
A customer may have more than three orders, requiring us to discard only the oldest ones.
Multiple customers can share the same name, so sorting by customer_id becomes necessary to break ties.
Since the problem guarantees one order per customer per day, ordering by order_date DESC is sufficient to determine recency.

Approaches

Brute Force Approach

A straightforward solution would be to process each customer independently.

We could first join the Customers and Orders tables, then for every customer:

Retrieve all of their orders.
Sort those orders by order_date in descending order.
Keep the first three entries.
Combine all results together.
Perform the final required sorting.

This approach produces the correct answer because it explicitly computes the most recent three orders for every customer.

However, the drawback is efficiency. If we repeatedly scan and sort orders customer by customer, we introduce unnecessary repeated work. In large datasets, repeatedly filtering the Orders table becomes expensive.

Optimal Approach, Window Function Ranking

The key insight is that we need to compute a ranking within each customer group.

Instead of processing customers one at a time, SQL provides a natural mechanism for this through window functions.

We can partition rows by customer_id and assign a ranking based on order_date DESC.

Using:

ROW_NUMBER() OVER (
    PARTITION BY customer_id
    ORDER BY order_date DESC
)

each customer’s orders receive rankings:

1 = newest order
2 = second newest
3 = third newest
and so on

Once ranked, we simply filter rows where rank <= 3.

This avoids repeated scans and sorting logic outside SQL. The database engine efficiently handles partitioning and ranking internally.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Group orders manually and sort per customer
Optimal	O(n log n)	O(n)	Uses SQL window function for per-customer ranking

Although both approaches involve sorting, the optimal solution leverages database execution engines and expresses the logic cleanly and efficiently.

Algorithm Walkthrough

Join the Customers and Orders tables using customer_id.

This gives us access to both customer names and order information in the same dataset. Since the final output requires customer names, the join is necessary. 2. Partition orders by customer.

We treat each customer independently because the problem asks for the most recent orders per customer, not globally. 3. Rank orders inside each customer group.

Use ROW_NUMBER() with:

PARTITION BY customer_id
ORDER BY order_date DESC

This assigns rank 1 to the newest order, rank 2 to the second newest, and so forth. 4. Keep only the top three orders.

Filter rows where the assigned row number is less than or equal to 3.

Customers with fewer than three orders naturally remain valid because all of their rows satisfy the condition. 5. Apply the final sorting.

Sort the final result using:

customer_name ASC
customer_id ASC
order_date DESC

Why it works

The correctness comes from the fact that ROW_NUMBER() establishes an exact ordering of orders within each customer partition. Since rows are ordered by descending order date, rank 1 always corresponds to the most recent order, rank 2 to the second most recent, and rank 3 to the third most recent. By filtering to ranks less than or equal to 3, we guarantee that every customer contributes only their three newest orders while preserving customers with fewer orders.

Python Solution

LeetCode Database problems use SQL rather than executable Python. Below is the correct MySQL solution.

# This problem is solved using SQL, not Python.
# Equivalent SQL query:

"""
WITH ranked_orders AS (
    SELECT
        c.name AS customer_name,
        c.customer_id,
        o.order_id,
        o.order_date,
        ROW_NUMBER() OVER (
            PARTITION BY o.customer_id
            ORDER BY o.order_date DESC
        ) AS rn
    FROM Customers c
    JOIN Orders o
        ON c.customer_id = o.customer_id
)

SELECT
    customer_name,
    customer_id,
    order_id,
    order_date
FROM ranked_orders
WHERE rn <= 3
ORDER BY
    customer_name ASC,
    customer_id ASC,
    order_date DESC;
"""

The solution starts by joining Customers and Orders so that each order is paired with the corresponding customer name.

Next, a Common Table Expression named ranked_orders computes a ranking for every order using ROW_NUMBER(). The partitioning ensures that rankings reset for each customer independently. The descending date order guarantees that newer orders receive smaller rank values.

After ranking, the outer query filters rows to retain only the first three orders for each customer.

Finally, the result is sorted according to the exact requirements of the problem statement.

Go Solution

Since this is a database problem, the solution is written in SQL rather than Go. Below is the LeetCode-submittable MySQL query.

/*
WITH ranked_orders AS (
    SELECT
        c.name AS customer_name,
        c.customer_id,
        o.order_id,
        o.order_date,
        ROW_NUMBER() OVER (
            PARTITION BY o.customer_id
            ORDER BY o.order_date DESC
        ) AS rn
    FROM Customers c
    JOIN Orders o
        ON c.customer_id = o.customer_id
)

SELECT
    customer_name,
    customer_id,
    order_id,
    order_date
FROM ranked_orders
WHERE rn <= 3
ORDER BY
    customer_name ASC,
    customer_id ASC,
    order_date DESC;
*/

Unlike algorithmic LeetCode problems, database problems do not require a Go function implementation. The same SQL query is submitted regardless of language preference. The only difference here is formatting the query inside a Go multiline comment for consistency.

Worked Examples

Example 1

Consider the following orders grouped by customer.

Customer	Orders by Date
Winston (1)	2020-08-03, 2020-07-31, 2020-07-15, 2020-06-10
Jonathan (2)	2020-08-07, 2020-08-01, 2020-07-30
Annabelle (3)	2020-08-01, 2020-07-31
Marwan (4)	2020-07-29
Khaled (5)	No orders

After applying ROW_NUMBER():

Customer	Order Date	Rank
Winston	2020-08-03	1
Winston	2020-07-31	2
Winston	2020-07-15	3
Winston	2020-06-10	4
Jonathan	2020-08-07	1
Jonathan	2020-08-01	2
Jonathan	2020-07-30	3
Annabelle	2020-08-01	1
Annabelle	2020-07-31	2
Marwan	2020-07-29	1

We filter rows where rank <= 3.

Winston’s oldest order receives rank 4, so it is excluded.

Jonathan has exactly three orders, so all are included.

Annabelle and Marwan have fewer than three orders, so every order remains.

Finally, sorting by customer name and order date gives:

customer_name	customer_id	order_id	order_date
Annabelle	3	7	2020-08-01
Annabelle	3	3	2020-07-31
Jonathan	2	9	2020-08-07
Jonathan	2	6	2020-08-01
Jonathan	2	2	2020-07-30
Marwan	4	4	2020-07-29
Winston	1	8	2020-08-03
Winston	1	1	2020-07-31
Winston	1	10	2020-07-15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting within partitions for window ranking
Space	O(n)	Ranking metadata and intermediate query results

The dominant cost comes from sorting orders within customer partitions to assign row numbers. Database engines often optimize this internally, but conceptually the complexity behaves like sorting grouped data.

Test Cases

# Since this is a SQL problem, test cases are conceptual validations.

# Case 1: Customer with more than three orders
# Expected: only the newest three orders returned
assert True

# Case 2: Customer with exactly three orders
# Expected: all three orders returned
assert True

# Case 3: Customer with fewer than three orders
# Expected: all orders returned
assert True

# Case 4: Customer with one order
# Expected: single row returned
assert True

# Case 5: Customer with no orders
# Expected: customer absent from result
assert True

# Case 6: Multiple customers with same name
# Expected: sorted by customer_id ascending
assert True

# Case 7: Orders already sorted differently
# Expected: output still sorted correctly
assert True

Test Summary

Test	Why
More than three orders	Ensures oldest orders are discarded
Exactly three orders	Validates boundary condition
Fewer than three orders	Ensures all available rows are returned
Single order	Verifies minimal valid input
No orders	Confirms join behavior
Duplicate customer names	Validates secondary sorting
Unordered input	Ensures ranking logic works regardless of input order

Edge Cases

Customer With Fewer Than Three Orders

A customer may have only one or two orders. A naive implementation might incorrectly require exactly three rows per customer or introduce null placeholders. The ranking approach handles this naturally because all rows receive ranks less than or equal to 3, so every order is preserved.

Customer With More Than Three Orders

This is the primary filtering case. A bug-prone implementation might accidentally keep the oldest three orders instead of the newest three. Ordering by order_date DESC ensures rank 1 is always the newest order, making the filter correct.

The problem explicitly requires sorting by customer_name, then customer_id. If two customers have identical names, relying only on the name field would produce unstable ordering. Including customer_id ASC guarantees deterministic results.

Customer With No Orders

Some customers may exist in Customers but never appear in Orders. Since the problem asks for customer orders, such customers should not appear in the output. Using an inner JOIN naturally excludes them.

Follow Up, Most Recent `n` Orders

The solution generalizes easily. Instead of filtering with:

WHERE rn <= 3

we simply replace 3 with a parameter n:

WHERE rn <= n

The ranking mechanism remains unchanged, making the approach scalable for any number of recent orders.