655. Stock Price Fluctuation
A price feed streams records of the form (timestamp, price) for a single stock. Records can arrive out of order, and a record whose timestamp was already seen is a correction: it overwrites whatever price was previously stored for that timestamp.
Build a StockPrice class with four operations:
update(timestamp, price)— record (or correct) the price at that timestamp.current()— return the price at the latest timestamp recorded so far.maximum()— return the highest price the stock has held at any timestamp, after all corrections.minimum()— return the lowest such price.
current, maximum, and minimum are only called after at least one update.
Example 1:
Input: update(1,10) · update(2,5) · current() · maximum() · update(1,3) · maximum() · update(4,2) · minimum()
Output: 5, 10, 5, 2
Explanation: After the first two updates the latest timestamp is 2, so current() = 5 and maximum() = 10. The correction update(1, 3) rewrites history — timestamp 1 was never really 10 — so maximum() drops to 5. After update(4, 2), minimum() = 2.
Example 2:
Input: update(10,40) · current() · update(5,25) · current() · minimum()
Output: 40, 40, 25
Explanation: The record for timestamp 5 arrives after the one for timestamp 10, but current() follows the latest *timestamp*, not the latest call — it stays 40. minimum() sees both prices and returns 25.
Constraints:
- 1 ≤ timestamp, price ≤ 10⁹
- At most 10⁵ operations in total
- current, maximum, and minimum are never called before the first update
- Updates may repeat a timestamp; the newest price for that timestamp wins
Hints:
A hash map timestamp → price plus the largest timestamp seen answers current() in O(1). The hard part is maximum()/minimum() under corrections.
A heap gives you the extreme price fast — but a correction can invalidate an entry buried inside it, and heaps don't support removing arbitrary elements.
Lazy deletion: push (price, timestamp) pairs and never remove eagerly. When you peek, check the map — if the map's price for that timestamp no longer matches the entry, the entry is stale; pop and try again.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: update(1,10) · update(2,5) · current() · maximum() · update(1,3) · maximum() · update(4,2) · minimum()
Expected output: 5, 10, 5, 2