You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.
Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.
Design an algorithm that:
Implement the StockPrice class:
StockPrice() Initializes the object with no price records.void update(int timestamp, int price) Updates the price of the stock at the given timestamp.int current() Returns the latest price of the stock.int maximum() Returns the maximum price of the stock.int minimum() Returns the minimum price of the stock.
Example 1:
Input
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]
Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5); // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current(); // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum(); // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3); // The previous timestamp 1 had the wrong price, so it is updated to 3.
// Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum(); // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2); // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum(); // return 2, the minimum price is 2 at timestamp 4.
Constraints:
1 <= timestamp, price <= 109105 calls will be made in total to update, current, maximum, and minimum.current, maximum, and minimum will be called only after update has been called at least once.Problem Overview: Design a data structure that processes a stream of stock price updates. Each update provides a timestamp and price. You must support correcting past prices, retrieving the latest price, and efficiently returning the maximum and minimum prices seen so far.
The challenge comes from corrections. A timestamp can appear multiple times, meaning the previous price for that timestamp becomes invalid. Your structure must update efficiently while still answering maximum() and minimum() queries quickly.
Approach 1: HashMap + SortedMap (Ordered Set) (O(log n) per update/query)
Store the latest price for each timestamp in a HashMap. This lets you detect corrections instantly. Maintain another structure that keeps prices sorted, typically a balanced tree such as TreeMap or a sorted multiset. When an update arrives, check if the timestamp already exists. If it does, decrement the frequency of the old price in the sorted structure before inserting the new one. Track the latest timestamp separately to answer current(). The smallest and largest keys in the sorted map give minimum() and maximum(). Updates and deletions both cost O(log n), while space usage is O(n). This approach relies on ordered structures commonly discussed in hash table and ordered set problems.
Approach 2: Priority Queues for Maximum and Minimum (Lazy Removal) (O(log n) per operation)
Instead of maintaining a fully sorted structure, keep two heaps: a max-heap for the maximum price and a min-heap for the minimum price. A HashMap still stores the latest price for each timestamp. Each update pushes the new (price, timestamp) pair into both heaps. Old values remain inside the heaps, which means they may become stale after corrections. Handle this with lazy deletion: whenever you query maximum() or minimum(), repeatedly pop from the heap until the top entry matches the current price stored in the hash map. Heap insertions and removals cost O(log n), and each outdated entry is removed once, giving efficient amortized performance. This design pattern appears often in heap (priority queue) and data stream problems.
Recommended for interviews: The priority queue approach is the most common interview solution because it demonstrates handling stale data with lazy deletion while maintaining fast queries. The HashMap + SortedMap solution is also strong and sometimes simpler in languages with built-in ordered maps like Java's TreeMap or C++ map. Showing awareness of corrections and maintaining consistent state is the key skill interviewers evaluate.
This approach utilizes a HashMap to store the price corresponding to each timestamp and a SortedMap to dynamically maintain the counts of each price, enabling efficient tracking of maximum and minimum prices. The HashMap allows quick updates and access to any timestamp's price, while the SortedMap keeps track of occurrences of each price value.
We maintain prices of each timestamp in a dictionary (timestamp_to_price), and use a SortedDict to keep track of the number of occurrences of each price (price_counts). Upon an update, if the timestamp already exists, we decrement the count of its old price. Then we update the timestamp with the new price and maintain the latest timestamp seen so far. Current, maximum, and minimum methods utilize the data structures to fetch results quickly.
Python
C++
Java
JavaScript
Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1).
Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price.
This approach uses a max heap (priority queue) for tracking the maximum price and a min heap for the minimum prices. Updates ensure that any obsolete prices are removed, and heap roots can quickly provide max/min prices. Furthermore, checks against the current timestamp allow discarding outdated entries efficiently.
In this solution, we maintain maxHeap for potential maximum prices and minHeap for potential minimum prices. Each update involves pushing the price to both heaps. Current retrieval from heaps requires cleaning invalid top entries until top reflects a valid timestamp. Thus, maximum and minimum methods traverse heap roots for the latest price associations using a heap invariant.
Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments.
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Using HashMap and SortedMap | Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1). Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price. |
| Using Priority Queues for Maximum and Minimum | Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments. Space Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + SortedMap (TreeMap / Ordered Map) | O(log n) per update and query | O(n) | Best when the language provides a built-in ordered map or multiset and you want clean min/max retrieval. |
| Two Priority Queues with Lazy Deletion | O(log n) amortized | O(n) | Preferred when heaps are easier to implement or when solving typical data stream problems. |
STOCK PRICE FLUCTUATION | LEETCODE # 2034 | PYTHON HEAP SOLUTION • Cracking FAANG • 4,569 views views
Watch 9 more video solutions →Practice Stock Price Fluctuation with our built-in code editor and test cases.
Practice on FleetCode