DSA problem
Stock Price Fluctuation
You are given a stream of records of a single stock's price at various timestamps. Records may arrive out of order, and a later record at the same timestamp corrects (overrides) the previous price for that timestamp. Implement a StockPrice class supporting four operations:
update(timestamp, price) records or corrects the price at timestamp. current() returns the price at the most recent timestamp seen so far. maximum() returns the maximum price across all (timestamp, price) records currently in effect. minimum() returns the minimum price across all records currently in effect. All four operations must run efficiently — ideally O(log n) per call.
The challenges are the out-of-order updates and the corrections. A simple hash map from timestamp to price handles current() in O(1) (just track latestTimestamp). For min/max, a heap that does not support efficient deletion would still work using lazy deletion, but the cleanest design uses a sorted multiset (or TreeMap of price -> count) that supports O(log n) insert, delete, and min/max lookups.
The optimal design therefore uses three structures: (1) timestampToPrice: Map<int, int> for current price at each timestamp; (2) priceCounts: TreeMap<int, int> mapping each price to the number of timestamps holding that price; and (3) latestTimestamp. On update(t, p): if t already has an old price, decrement its count (and remove the entry if it falls to zero); then set the new mapping and increment priceCounts[p]; if t >= latestTimestamp, update latestTimestamp and remember current is p. Min/max read the first/last key of priceCounts in O(log n).
Examples
["StockPrice","update","update","current","maximum","update","maximum","update","minimum"] [[],[1,10],[2,5],[],[],[1,3],[],[4,2],[]][null,null,null,5,10,null,5,null,2]["StockPrice","update","update","minimum","update","maximum"] [[],[1,1],[2,2],[],[1,3],[]][null,null,null,1,null,3]["StockPrice","update","current","update","current"] [[],[5,100],[],[3,50],[]][null,null,100,null,100]Constraints
- 1 <= timestamp, price <= 10^9
- At most 10^5 calls will be made to update, current, maximum, minimum (combined).
- current, maximum, minimum will be called only after at least one update.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.