Domain 2MediumMEDIUM

Product Price at a Given Date

Retrieve the latest price for each product on or before a specific target date using filtering and grouping.

Domain: medium•Updated: 2026-09-09
#filtering#groupby#O(N log N)#pandas

Problem Breakdown

The objective is to query historical pricing data (Products table) to find the valid new_price for every product_id as of a given target_date.

Inputs:

  • A DataFrame containing columns: product_id, new_price, change_date.
  • A string representing the target date (e.g., ‘2019-08-16’).

Outputs:

  • A list or DataFrame mapping each existing product_id to its price valid on that specific day. If a product has no recorded change before this date, it is typically excluded in standard LC test cases unless an initial default price exists (not present here).

Intuition

This problem follows the “Latest Value” pattern. For every partition (product_id), we need to identify the row with the maximum change_date that satisfies the condition change_date <= target_date.

Using Pandas, this is efficiently achieved by:

  1. Filtering: Restrict rows where change_date falls within our query window (on or before).
  2. Sorting & Grouping: Within each product group, sort by date descending to bring the most recent valid record to the top of its partition.
  3. Selection: Select the first row per group after sorting, which corresponds to the latest price <= target_date.

Approach

  1. Parse Dates: Convert input string and column dates into datetime objects for consistent comparison.
  2. Filter Valid Rows: Create a subset of rows where change_date is less than or equal to the parsed target_date. This ensures we only look at prices effective up to that day.
  3. Sort by Recency: Sort the filtered data by product_id (ascending) and then change_date (descending). This places the most recent valid price for each product first within its group.
  4. Aggregate & Select: Use groupby('product_id').first() to grab that top row per ID. Reset index and select specific columns (product_id, new_price).
  5. Final Sort: Ensure the result is sorted by product_id ascending, as required for deterministic output ordering in LeetCode environments.

Complexity Analysis

  • Time Complexity: O(N log N), where N is the number of rows in the DataFrame. This accounts for sorting (sort_values) which dominates linear operations like filtering and grouping (which are generally hash-based or scan-based). Filtering takes O(N) but sort adds a logarithmic factor relative to row count per partition.
  • Space Complexity: O(M), where M is the number of distinct products, plus auxiliary space for intermediate filtered/sorted DataFrames. In worst case scenarios involving large datasets without index optimization, this could approach O(N).

Solution

import pandas as pd

def get_product_prices(products_df: pd.DataFrame, target_date_str: str):
    """
    Returns a DataFrame with product_id and new_price valid on target_date_str.
    
    Args:
        products_df (pd.DataFrame): Columns ['product_id', 'new_price', 'change_date']
                                   change_date is assumed to be datetime or comparable string YYYY-MM-DD.
        target_date_str (str): The date for which we want the price in format 'YYYY-MM-DD'.

    Returns:
        pd.DataFrame with columns [product_id, new_price] sorted by product_id ascending.
    """
    
    # Ensure dates are parsed to datetime objects if they aren't already
    products_df['change_date'] = pd.to_datetime(products_df['change_date'])
    target_date = pd.Timestamp(target_date_str)

    # Filter rows where the price change happened on or before the target date
    valid_records = products_df[products_df['change_date'] <= target_date]

    if valid_records.empty:
        return pd.DataFrame(columns=['product_id', 'new_price'])

    # Sort by product_id ascending, then descending by date to get latest price first per group
    sorted_valid = valid_records.sort_values(
        by=['product_id', 'change_date'], 
        ascending=[True, False]
    )

    # Select the top row for each product (the most recent one <= target)
    result_df = sorted_valid.groupby('product_id').first().reset_index()

    return result_df[['product_id', 'new_price']].sort_values(by='product_id')

Edge Cases Handled

  • Empty Input: Returns an empty DataFrame with correct columns if no valid records exist.
  • Date Parsing: Handles string dates by converting to Timestamp objects, ensuring accurate comparison regardless of input format variations (assuming YYYY-MM-DD).
  • Multiple Changes Same Day: Sorting logic ensures any row on the exact target date is considered; since we filter <=, all valid changes up to that day are included. The sort order picks one deterministically if multiple exist for same ID/Date, though LC schema usually implies unique dates per product or consistent ordering.
  • Output Ordering: Explicitly sorts final result by product_id ascending to match LeetCode output requirements regardless of internal groupby iteration order in different Pandas versions.