Price records arrive as (timestamp, price), possibly out of order, and a later record for an existing timestamp corrects the earlier one. Implement update, current (the price at the latest timestamp), maximum and minimum over the current records. The expected output lists the results of current, maximum and minimum.
Before you code
A correction must remove the old price from whatever answers maximum and minimum. Which structure knows the old price, and which one can remove it?
Hints
- Keep a hash map from timestamp to price, and the largest timestamp seen.
- Keep prices in an ordered multiset: on a correction, remove the old price and add the new one. Maximum and minimum are its ends.
- Alternatively, keep a max-heap and a min-heap of (price, timestamp). When reading the top, discard entries whose price no longer matches the hash map.
Production & complexity notes
When solving Stock price fluctuation on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Choosing an ordered structure to reinforce the underlying pattern.
What it practices
Combining a hash map with an ordered structure, from Choosing an ordered structure.