Domain 2MediumMEDIUM

The Most Recent Three Orders

Groups orders by customer, sorts each group's top 3 recent dates, and globally sorts the final result list to ensure descending order of recency.

Domain: medium•Updated: 2026-09-18
#Grouping#Sorting#O(N log N)#O(N)

Problem Breakdown

Restatement: We need to identify, for every customer who has placed orders, their three most recent transactions based on order_date. If a specific customer has fewer than three orders in total, we return all available records. The final result must be sorted by the order_date descending globally (most recent first across all customers).

Inputs:

  • A list of dictionaries representing rows from an implicit Orders table containing at least customer_id and order_date.

Outputs:

  • A list of lists, where each inner list represents a record [customer_id, order_date], sorted globally by date descending.

Implicit Constraints & Edge Cases:

  1. Fewer than three orders: The logic must handle customers with < 3 orders without error; simply return all available rows in the correct global sort order.
  2. Global Sorting Requirement: Unlike standard SQL window functions which might output per-group, Python lists require explicit sorting of the final collection to meet the “sorted by order_date descending” requirement stated in the problem description. The proposed solution missed this step initially.
  3. Tie-breaking on dates: If multiple orders share the exact same timestamp, standard sort stability preserves relative order; consistent ordering is acceptable unless specified otherwise.
  4. Empty Input: The code must handle scenarios where no customers or orders exist gracefully (return empty list).

Intuition

Brute Force Approach: A naive approach might iterate through every customer, filter their specific order history from the global dataset for each one individually, sort that subset, and slice it. If implemented inefficiently (e.g., scanning a large list repeatedly), this could degrade to O(N^2). Even if we scan once per customer, sorting dominates complexity.

Key Insight: The core operation is grouping by customer_id followed by local sorting within each group. Since the requirement is strictly “top 3”, we don’t need to sort globally and then partition; however, unlike SQL where window functions handle this natively, Python requires explicit post-processing for global ordering if specified. Grouping into buckets (using a hash map) followed by sorting each bucket is the most direct translation of “window function” behavior using standard libraries.

Optimal Approach:

  1. Grouping: Aggregate orders by customer_id. This takes linear time O(N).
  2. Sorting & Slicing: For each customer’s list, sort descending by date and take the first three elements. Sorting a subset of size kk is efficient; worst case (one giant group) remains dominated by sorting complexity.
  3. Global Ordering: Collect all selected records into a single result list and perform one final global sort to satisfy the output ordering requirement, which adds negligible overhead compared to grouping/sorting steps in most distributions but ensures correctness for edge cases where customers are processed out of date order.

Approach

  1. Initialize a defaultdict to map customer_id -> List of dictionaries containing {order_date}.
  2. Iterate through the provided orders list, populating this dictionary. This groups all data logically in O(N).
  3. Create an empty result list.
  4. For each customer ID found:
    • Extract their order history from the map.
    • Sort that specific list by order_date descending (using a key function and reverse flag).
    • Slice the first three items ([:3]).
  5. Format these sliced records into [customer_id, date] tuples/lists and append to our result set.
  6. Crucial Step: Sort the entire result list by order_date descending before returning to ensure global compliance with problem requirements.
  7. Return the aggregated results.

Complexity Analysis

  • Time: O(N log N) in the worst case (where all orders belong to a single customer). The grouping step is O(N), and sorting dominates with complexity proportional to Nlog⁡NN \log N. If data were distributed evenly across customers, it would be faster on average but bounded by this upper limit. The final global sort of at most 3*K items adds negligible overhead (O(Klog⁡K)O(K \log K) where KK is unique customers).
  • Space: O(N) to store the map keys and values (M orders stored in memory for grouping before processing), plus space for the result list which contains at most 3*N elements. This fits within standard interview constraints given typical input sizes (N≤105N \le 10^5).

Solution

from collections import defaultdict
from typing import List, Dict, Any

def get_recent_orders(orders: List[Dict[str, Any]]) -> List[List[Any]]:
    """
    Returns the most recent three orders for each customer.
    
    Args:
        orders: A list of dictionaries representing rows from the Orders table. 
                Expected keys include 'customer_id' and 'order_date'.
                
    Returns:
        A list of lists, where each inner list represents an order record [id, date].
        The result is sorted globally by order_date descending as per requirements.
    """
    
    # Step 1: Group orders by customer_id using defaultdict for O(N) insertion
    if not orders:
        return []

    customer_orders = defaultdict(list)
    for order in orders:
        cid = order['customer_id']
        date = order['order_date']
        # Store the specific record info needed later
        customer_orders[cid].append({'order_date': date})

    result = []
    
    # Step 2 & 3: Iterate through each customer's order history
    for cid in customer_orders:
        orders_list = customer_orders[cid]
        
        # Sort by 'order_date' descending to get most recent first. 
        sorted_orders = sorted(orders_list, key=lambda x: x['order_date'], reverse=True)
        
        # Step 4 & 5: Take top 3 (or all if fewer than 3 exist naturally via slicing)
        recent_three = sorted_orders[:3]
        
        # Format output to match expected return structure [customer_id, order_date] 
        for o in recent_three:
            result.append([cid, o['order_date']])

    # Step 6: Global sort required by problem statement "sorted by the `order_date` descending"
    result.sort(key=lambda x: x[1], reverse=True)

    return result

Edge Cases Handled

  • Empty Input: Returns an empty list immediately if input is null or empty.
  • Fewer than three orders: Slicing with [:3] naturally handles customers with 0, 1, or 2 orders without index errors.
  • Global Sort Order: The final sort ensures that even if customers are processed in arbitrary order (dict insertion), the output is strictly sorted by date descending globally.
  • Date Ties: Python’s sorted() is stable; ties on dates maintain relative input order, which satisfies standard LC acceptance criteria unless specific tie-breaking rules exist.