Stock Price Fluctuation
Medium · Trees · Hash Table · Design · Heap (Priority Queue) · Ordered Set · Data Stream
Problem
You receive a stream of price records for a stock, each a (timestamp, price) pair. Records may arrive out of order, and a later record for a timestamp that already exists corrects (replaces) the earlier price.
Implement StockPrice:
- StockPrice() creates an object with no records.
- update(timestamp, price) records or corrects the price at timestamp.
- current() returns the price at the latest timestamp seen so far.
- maximum() returns the highest price across all current records.
- minimum() returns the lowest price across all current records.
The input is the list of operations and the list of their arguments, and the output lists what each call returns (null for the constructor and for update).
Examples
Input: ops = ["StockPrice","update","update","current","maximum","update","maximum","minimum"], args = [[],[3,20],[1,50],[],[],[1,10],[],[]] Output: [None, None, None, 20, 50, None, 20, 10]
Timestamp 3 is the latest, so current is 20. Correcting timestamp 1 from 50 to 10 makes the maximum 20 and the minimum 10.
Input: ops = ["StockPrice","update","minimum","update","current"], args = [[],[7,4],[],[9,6],[]] Output: [None, None, 4, None, 6]
After the second update, timestamp 9 is the latest.
Input: ops = ["StockPrice","update","update","current","maximum"], args = [[],[8,5],[2,30],[],[]] Output: [None, None, None, 5, 30]
Timestamp 2 arrives after 8, so current stays 5, but 30 is the new maximum.
Constraints
- 1 <= timestamp, price <= 10^9
- At most 10^5 calls are made in total to update, current, maximum and minimum
- current, maximum and minimum are called only after at least one update
Approaches
- Dictionary, scan on every query — time O(1) update, O(k) per query, space O(k), k = distinct timestamps
Follow-up
Lazy heaps can grow with every update, even when most entries are stale. If memory matters, a sorted multiset keeps exactly one entry per timestamp; the Java and C++ versions here use one. In Python, sortedcontainers.SortedList plays that role.
Related problems
Start free on Cariara · Coding problems · System design studio
