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.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.
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.
C++
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) |
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python • NeetCode • 848,237 views views
Watch 9 more video solutions →Practice Stock Price Fluctuation with our built-in code editor and test cases.
Practice on FleetCode