Stock Price Fluctuation LeetCode 2034

LeetCode 2034 asks you to implement a StockPrice class that processes a stream of stock price records. Each record is a (timestamp, price) pair. The catch: updates can correct previously seen timestamps, meaning the price at a given timestamp can change over time.

Your class must support four operations efficiently. First, update(timestamp, price) records the latest price for a given timestamp. Second, current() returns the price at the most recent (highest) timestamp seen so far. Third, maximum() returns the highest price among all current prices across all timestamps. Fourth, minimum() returns the lowest price across all timestamps.

The constraints allow up to 100,000 calls, so naive O(n) scans for max and min will time out. You need a design that handles corrections to past prices without blowing up the time complexity.

A naive approach might keep a running max and min. On each update, if the new price is larger than the current max, update the max — similarly for min. This works fine as long as prices only arrive in order and are never corrected.

The problem is corrections. Suppose timestamp 5 was recorded with price 100, making it the global maximum. Then a correction arrives: timestamp 5 is now price 30. Your running max is stale — 100 is no longer a valid price for any timestamp, but you have no efficient way to know what the new maximum should be without scanning all stored prices.

This invalidation problem rules out any approach that only maintains a single running value. You need a structure that lets you query the true current maximum and minimum even after arbitrary corrections to past timestamps.

The standard solution combines three data structures. A HashMap (prices) maps each timestamp to its current price. A max-heap stores (price, timestamp) pairs and lets you query the highest price in O(log n). A min-heap stores the same pairs in reverse order and lets you query the lowest price in O(log n).

On each update call, you store the new (timestamp, price) in the HashMap and push the pair into both heaps. You do not remove the old price from the heaps — that would require O(n) time for an arbitrary heap. Instead you use lazy deletion.

When querying maximum() or minimum(), you peek at the heap top. If the price stored in the heap matches what the HashMap says is the current price for that timestamp, the entry is valid. If it does not match, the timestamp has been corrected and that heap entry is stale — pop it and check the next one.

Lazy deletion is a technique where you avoid the expensive work of removing an element from a heap when it becomes invalid. Instead, you leave stale entries in place and only discard them when they surface at the top of the heap during a query.

In this problem, every time a timestamp is corrected, the old (price, timestamp) pair in the heap becomes stale. Rather than hunting it down in O(n) and re-heapifying, you simply push the new entry and move on. The stale entry remains buried somewhere in the heap.

When you call maximum() or minimum(), you check if the heap top is consistent with the HashMap. If prices[timestamp] differs from what is stored in the heap, that entry is from an old correction and you pop it. You keep popping until you find an entry that matches — and that is your true current max or min.

Python's SortedList from the sortedcontainers library provides a cleaner solution. A SortedList maintains all elements in sorted order and supports O(log n) add, remove, min, and max. It is essentially a balanced BST with list-like indexing.

On each update call, if the timestamp already exists in the HashMap, you remove the old price from the SortedList before inserting the new one. Then update the HashMap. This way, the SortedList always contains exactly the current prices — no stale entries, no lazy deletion needed.

The downside is that sortedcontainers is a third-party library not available in all interview environments or languages. In Java you would use a TreeMap with price → count of timestamps at that price, which handles duplicates properly. The heap approach is more portable and is the idiomatic Python solution in interviews.

In Python, the max-heap is simulated by pushing negative prices (since Python's heapq is a min-heap). Push (-price, timestamp) for the max-heap and (price, timestamp) for the min-heap. Track maxTimestamp as a plain integer updated on each update() call. The current() method simply returns self.prices[self.maxTimestamp].

For maximum(): while the heap top's price does not match self.prices[top_timestamp], pop. The price stored in the heap is negative for the max-heap, so compare -heap[0][0] against self.prices[heap[0][1]]. Return -heap[0][0] when they agree. The minimum() implementation mirrors this using the min-heap directly.

In Java, use two PriorityQueues. The max-heap uses a comparator that reverses natural order. Use a TreeMap<Integer, Integer> (timestamp → price) as the HashMap and track the last key via treeMap.lastKey() for current(). On each maximum()/minimum() call, poll the heap while the polled price does not match the map value for that timestamp.

Stock Price Fluctuation belongs to the online query design family — problems where you maintain a data structure under a stream of updates and must answer queries at any point. The correction aspect links it closely to Time-Based Key-Value Store (LeetCode 981), where you also map timestamps to values and query the most recent one at or before a given time.

The sliding window median (LeetCode 480) uses the same two-heap-with-lazy-deletion motif. There you maintain a max-heap for the lower half and a min-heap for the upper half of a sliding window, rebalancing as elements enter and leave. Design Hit Counter and Design Circular Queue are simpler relatives in the design family that do not require heap-based lazy deletion.

If you are comfortable with the heap approach for 2034, try the SortedList / TreeMap variant and then attack Sliding Window Median to see lazy deletion under more pressure. The heap and lazy deletion pattern also appears in meeting room scheduling and task scheduler problems where you process intervals or events in priority order.