Product Price at a Given Date

medium hash map sorting dates

Problem

Each change row says a product's price became new_price on change_date. Every product starts at the default price 10 before any change. Given a target date, return the price of each product as of that date — the most recent change on or before the target, or 10 if there is none yet.

Inputchanges = [(1,20,"08-15"),(1,35,"08-17"),(2,50,"08-14"),(3,99,"08-20")], target = "08-16"

Output{1: 20, 2: 50, 3: 10}

Product 1's latest change on/before 08-16 is the 08-15 row (price 20); the 08-17 change is in the future. Product 2 settled to 50 on 08-14. Product 3 has no change yet on 08-16, so it keeps the default 10.

changes (id:price:MM-DD, comma-separated)

target date (MM-DD)

def prices_on(changes, target):
    changes.sort(key=lambda c: c[2])
    price = {}
    for pid, new_price, date in changes:
        if date <= target:
            price[pid] = new_price
    for pid, _, _ in changes:
        price.setdefault(pid, 10)
    return price

function pricesOn(changes, target) {
  changes.sort((a, b) => (a[2] < b[2] ? -1 : a[2] > b[2] ? 1 : 0));
  const price = new Map();
  for (const [pid, newPrice, date] of changes) {
    if (date <= target) price.set(pid, newPrice);
  }
  for (const [pid] of changes) {
    if (!price.has(pid)) price.set(pid, 10);
  }
  return price;
}

Map<Integer, Integer> pricesOn(int[][] changes, String[] dates, String target) {
    Integer[] idx = sortByDate(changes, dates);  // indices sorted by date
    Map<Integer, Integer> price = new HashMap<>();
    for (int i : idx) {
        if (dates[i].compareTo(target) <= 0)
            price.put(changes[i][0], changes[i][1]);
    }
    for (int i : idx)
        price.putIfAbsent(changes[i][0], 10);
    return price;
}

map<int,int> pricesOn(vector<tuple<int,int,string>>& changes, string target) {
    sort(changes.begin(), changes.end(),
         [](auto& a, auto& b){ return get<2>(a) < get<2>(b); });
    map<int,int> price;
    for (auto& [pid, np, date] : changes)
        if (date <= target) price[pid] = np;
    for (auto& [pid, np, date] : changes)
        if (!price.count(pid)) price[pid] = 10;
    return price;
}

Explanation

Each product's price on the target date is its most recent change on or before that date, and 10 if nothing has happened yet. We get this by applying changes in chronological order and letting later ones overwrite earlier ones.

First we sort the changes by date. Then we walk them and, whenever date <= target, we set price[pid] = new_price. Because we go oldest-first, the last qualifying change wins and lands in the map — exactly the most recent one.

Future changes (date after the target) are simply skipped, so they cannot affect the answer.

A second short pass uses setdefault(pid, 10) to give the default 10 to any product that never had a qualifying change.

Example: target 08-16. Product 1 has 08-15 (price 20) and 08-17 (price 35); only 08-15 qualifies → 20. Product 2 settled to 50 on 08-14 → 50. Product 3's only change is 08-20 (future) → default 10. Result: {1: 20, 2: 50, 3: 10}.

Time: O(n log n) Space: O(n)