We're building a stock price tracker that handles a stream of records arriving out of order. Sometimes a correction comes in that overwrites a previous price at the same timestamp. At any point, we need to answer three questions: what's the most recent price, what's the highest price across all timestamps, and what's the lowest?

The current price is straightforward if we track which timestamp is the latest. The harder part is maintaining the maximum and minimum efficiently when corrections happen. If timestamp 1's price changes from 10 to 3, and 10 was the maximum, decrementing a counter is not enough. We have to find the new maximum after removing 10 from consideration.

That correction is what separates this from a plain "running max/min" problem. We need a data structure that supports both adding new prices and removing old ones when they get corrected, while still answering max and min queries quickly.

Key Constraints:

Intuition

Store the latest price for each timestamp in a hash map, and track which timestamp is the most recent. For current, look up the latest timestamp's price. For maximum and minimum, scan through all stored prices.

This is correct, but the scan is the bottleneck. Every max/min query walks through every timestamp seen so far, which is O(n) per query.

Algorithm

Example Walkthrough

Code

Each maximum or minimum call scans all n stored prices. The next approach maintains the extremes incrementally as prices are added and corrected, so a query no longer rescans everything.

Intuition

A max-heap keeps the largest element on top and a min-heap keeps the smallest, both readable in O(1). The complication is corrections: when a timestamp's price gets corrected, the old price is still buried somewhere inside the heap, and a binary heap cannot remove an arbitrary interior element efficiently.

Lazy deletion sidesteps this. Instead of removing the stale entry when a correction happens, we leave it in the heap and push the new price as a separate entry. When we read the top, we check whether its price still matches the hash map for that timestamp. If it doesn't, the entry is stale, so we pop it and check the next one, repeating until the top is valid.

A stale entry is safe to ignore because the hash map always holds the authoritative current price for each timestamp. An entry (price, timestamp) is current only when priceMap[timestamp] == price, so the validity check never discards a live maximum or minimum.

Algorithm

Example Walkthrough

Code

The heap approach accumulates stale entries until they reach the top. The next approach removes a corrected price the moment it happens, so the structure never holds anything stale.

Intuition

A sorted structure mapping each price to how many timestamps currently hold that price keeps the data consistent at all times. Adding a price increments its count. A correction decrements the old price's count, removing the key entirely when the count reaches zero, and increments the new price's count. The minimum is the smallest key and the maximum is the largest key.

A balanced BST such as Java's TreeMap supports this directly: O(log n) for insert and delete, and O(log n) to read the first key (minimum) or last key (maximum). Because corrected prices are removed immediately, the structure never carries stale entries, so a query reads an extreme without any cleanup pass.

The frequency count is what makes deletion correct when several timestamps share a price. If two timestamps both hold price 5, the key 5 has count 2, and correcting one of them drops the count to 1 rather than removing 5 outright. The key disappears only when no timestamp holds that price.

Algorithm

Example Walkthrough

Code