Stock Price Fluctuation
MedPrompt
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:
- Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
- Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
- Finds the maximum price the stock has been based on the current records.
- Finds the minimum price the stock has been based on the current records.
Implement the StockPrice class:
StockPrice()Initializes the object with no price records.void update(int timestamp, int price)Updates thepriceof the stock at the giventimestamp.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 <= 109- At most
105calls will be made in total toupdate,current,maximum, andminimum. current,maximum, andminimumwill be called only afterupdatehas been called at least once.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by using a TreeMap to store the timestamp-price data. A TreeMap keeps its keys (timestamps) sorted, which allows for efficient retrieval of the latest price, but finding the minimum and maximum prices still requires a full scan.
Algorithm
- Initialize a
TreeMap<Integer, Integer>to store timestamp-price records, which keeps them sorted by timestamp. - For
update(timestamp, price), usemap.put(timestamp, price). This takes O(log N) time. - For
current(), retrieve the last key (the maximum timestamp) from theTreeMapusinglastKey()and get its value. This takes O(log N) time. - For
maximum()andminimum(), iterate through all values in theTreeMap, which still takes O(N) time.
Walkthrough
By replacing the HashMap with a TreeMap<Integer, Integer>, we can optimize the current() operation. A TreeMap is a sorted map that maintains its entries in ascending order of keys.
update(timestamp, price): We insert or update the key-value pair in theTreeMap. This operation takes O(log N) time, as the map needs to maintain its sorted order.current(): Since theTreeMapis sorted by timestamp, the latest timestamp is simply the last key in the map. We can retrieve this usingrecords.lastKey()in O(log N) time and then get its corresponding price.maximum(): To find the maximum price, we still need to iterate through all the values in theTreeMap. This remains an O(N) operation.minimum(): Similarly, finding the minimum price requires iterating through all values, taking O(N) time.
class StockPrice { TreeMap<Integer, Integer> records; public StockPrice() { records = new TreeMap<>(); } public void update(int timestamp, int price) { records.put(timestamp, price); } public int current() { // lastKey() gives the highest timestamp in O(log N) return records.get(records.lastKey()); } public int maximum() { int maxPrice = 0; for (int price : records.values()) { maxPrice = Math.max(maxPrice, price); } return maxPrice; } public int minimum() { int minPrice = Integer.MAX_VALUE; for (int price : records.values()) { minPrice = Math.min(minPrice, price); } return minPrice; }}Complexity
Time
- `update`: O(log N). - `current`: O(log N). - `maximum`: O(N). - `minimum`: O(N).
Space
O(N), where N is the number of unique timestamps, to store the records in the `TreeMap`.
Trade-offs
Pros
The
current()operation is significantly faster (O(log N)) than in the brute-force approach.The implementation is still relatively simple.
Cons
The
maximum()andminimum()operations remain inefficient with O(N) time complexity.The
updateoperation is slightly slower (O(log N)) than the pureHashMapapproach (O(1)).
This approach uses a HashMap to store the timestamp-price data. While update operations are efficient, retrieving the current, maximum, or minimum price requires iterating through all the stored records, making it the least efficient method for query operations.
Algorithm
- Initialize a
HashMap<Integer, Integer>to store timestamp-price records. - For
update(timestamp, price), simply usemap.put(timestamp, price). - For
current(), iterate through all keys in theHashMapto find the maximum timestamp, then retrieve its price. This takes O(N) time. - For
maximum(), iterate through all values in theHashMapto find the maximum price. This takes O(N) time. - For
minimum(), iterate through all values in theHashMapto find the minimum price. This also takes O(N) time.
Walkthrough
In this straightforward approach, we use a HashMap<Integer, Integer> to map each timestamp to its price. The update operation is very fast, as it's a standard hash map insertion or update.
update(timestamp, price): We insert or update the key-value pair in theHashMap. This is an average O(1) operation.current(): To find the price at the latest timestamp, we must iterate through all the keys (timestamps) in theHashMapto find the maximum timestamp. Then, we retrieve the price associated with this timestamp. This is an O(N) operation, where N is the number of unique timestamps.maximum(): To find the maximum price, we iterate through all the values (prices) in theHashMapand keep track of the maximum one found. This is an O(N) operation.minimum(): Similarly, we iterate through all the values to find the minimum price, which is also an O(N) operation.
class StockPrice { HashMap<Integer, Integer> records; int latestTimestamp; public StockPrice() { records = new HashMap<>(); latestTimestamp = 0; } public void update(int timestamp, int price) { records.put(timestamp, price); // Note: This simple tracking of latestTimestamp is not sufficient // because we need to find the true max key on each 'current' call // in case updates are out of order. } public int current() { int maxTimestamp = 0; for (int timestamp : records.keySet()) { maxTimestamp = Math.max(maxTimestamp, timestamp); } return records.get(maxTimestamp); } public int maximum() { int maxPrice = 0; for (int price : records.values()) { maxPrice = Math.max(maxPrice, price); } return maxPrice; } public int minimum() { int minPrice = Integer.MAX_VALUE; for (int price : records.values()) { minPrice = Math.min(minPrice, price); } return minPrice; }}Complexity
Time
- `update`: O(1) on average. - `current`: O(N), where N is the number of records. - `maximum`: O(N). - `minimum`: O(N).
Space
O(N), where N is the number of unique timestamps. We need to store each timestamp-price pair in the `HashMap`.
Trade-offs
Pros
Very simple to understand and implement.
The
updateoperation is highly efficient with an average time complexity of O(1).
Cons
The
current(),maximum(), andminimum()operations have a linear time complexity of O(N), which can be very slow if the number of records (N) is large.This approach will likely lead to a 'Time Limit Exceeded' error on platforms with strict time constraints for this type of problem.
This is the most efficient approach, utilizing two TreeMap data structures to optimize all operations. One TreeMap stores timestamp-to-price mappings for efficient current() lookups, and a second TreeMap stores price frequencies for efficient minimum() and maximum() lookups. All operations achieve logarithmic time complexity.
Algorithm
- Use two
TreeMaps:timestampToPriceto map timestamps to prices, andpriceToCountto map prices to their frequencies. - For
update(timestamp, price):- If the timestamp exists, find the
oldPrice, and decrement its count inpriceToCount. If the count becomes zero, remove theoldPriceentry. - Update
timestampToPricewith the new price. - Increment the count of the new
priceinpriceToCount.
- If the timestamp exists, find the
- For
current(): Get the last key fromtimestampToPriceand return its value. - For
maximum(): Return the last key frompriceToCount. - For
minimum(): Return the first key frompriceToCount.
Walkthrough
To achieve optimal performance for all operations, we use two TreeMaps:
TreeMap<Integer, Integer> timestampToPrice: This maps timestamps to their prices. Being sorted by timestamp, it allows us to find thecurrentprice in O(log N) time.TreeMap<Integer, Integer> priceToCount: This maps prices to their frequencies (how many times each price appears). Being sorted by price, it allows us to find theminimumandmaximumprices in O(log P) time, where P is the number of unique prices.
update(timestamp, price): When updating, we must keep both maps consistent. If a timestamp is being updated, we first find its old price fromtimestampToPrice. We then decrement the count of this old price inpriceToCount. If the count drops to zero, we remove the price frompriceToCount. After handling the old price, we updatetimestampToPricewith the new price and increment the new price's count inpriceToCount.current(): The latest price corresponds to the highest timestamp, which is the last key intimestampToPrice. This is an O(log N) operation.maximum(): The maximum price is the highest price recorded, which is the last key inpriceToCount. This is an O(log P) operation.minimum(): The minimum price is the lowest price recorded, which is the first key inpriceToCount. This is an O(log P) operation.
class StockPrice { // Stores timestamp -> price, sorted by timestamp private TreeMap<Integer, Integer> timestampToPrice; // Stores price -> count of that price, sorted by price private TreeMap<Integer, Integer> priceToCount; public StockPrice() { timestampToPrice = new TreeMap<>(); priceToCount = new TreeMap<>(); } public void update(int timestamp, int price) { // If the timestamp already exists, we are correcting a price. if (timestampToPrice.containsKey(timestamp)) { int oldPrice = timestampToPrice.get(timestamp); // Decrement the count of the old price. priceToCount.put(oldPrice, priceToCount.get(oldPrice) - 1); // If the count becomes zero, remove the price from the map. if (priceToCount.get(oldPrice) == 0) { priceToCount.remove(oldPrice); } } // Update the timestamp with the new price. timestampToPrice.put(timestamp, price); // Increment the count of the new price. priceToCount.put(price, priceToCount.getOrDefault(price, 0) + 1); } public int current() { // The last key in the timestamp map is the latest timestamp. return timestampToPrice.get(timestampToPrice.lastKey()); } public int maximum() { // The last key in the price map is the maximum price. return priceToCount.lastKey(); } public int minimum() { // The first key in the price map is the minimum price. return priceToCount.firstKey(); }}Complexity
Time
- `update`: O(log N), where N is the number of records. - `current`: O(log N). - `maximum`: O(log P), where P is the number of unique prices. - `minimum`: O(log P).
Space
O(N), where N is the number of unique timestamps. Each record is stored in `timestampToPrice`, and each unique price and its count are stored in `priceToCount`.
Trade-offs
Pros
All operations (
update,current,maximum,minimum) are highly efficient, with logarithmic time complexity.This approach is scalable and will perform well even with a large number of records and calls.
Cons
The implementation is more complex due to the need to manage two data structures and keep them synchronized.
It consumes more memory than the other approaches because of the overhead of two
TreeMaps.
Solutions
Solution
class StockPrice { private Map < Integer , Integer > d = new HashMap <>(); private TreeMap < Integer , Integer > ls = new TreeMap <>(); private int last ; public StockPrice () { } public void update ( int timestamp , int price ) { if ( d . containsKey ( timestamp )) { int old = d . get ( timestamp ); if ( ls . merge ( old , - 1 , Integer: : sum ) == 0 ) { ls . remove ( old ); } } d . put ( timestamp , price ); ls . merge ( price , 1 , Integer: : sum ); last = Math . max ( last , timestamp ); } public int current () { return d . get ( last ); } public int maximum () { return ls . lastKey (); } public int minimum () { return ls . firstKey (); } } /** * Your StockPrice object will be instantiated and called as such: * StockPrice obj = new StockPrice(); * obj.update(timestamp,price); * int param_2 = obj.current(); * int param_3 = obj.maximum(); * int param_4 = obj.minimum(); */class StockPrice { public: StockPrice () { } void update ( int timestamp , int price ) { if ( d . count ( timestamp )) { ls . erase ( ls . find ( d [ timestamp ])); } d [ timestamp ] = price ; ls . insert ( price ); last = max ( last , timestamp ); } int current () { return d [ last ]; } int maximum () { return * ls . rbegin (); } int minimum () { return * ls . begin (); } private: unordered_map < int , int > d ; multiset < int > ls ; int last = 0 ; }; /** * Your StockPrice object will be instantiated and called as such: * StockPrice* obj = new StockPrice(); * obj->update(timestamp,price); * int param_2 = obj->current(); * int param_3 = obj->maximum(); * int param_4 = obj->minimum(); */from sortedcontainers import SortedList class StockPrice : def __init__ ( self ): self . d = {} self . ls = SortedList () self . last = 0 def update ( self , timestamp : int , price : int ) -> None : if timestamp in self . d : self . ls . remove ( self . d [ timestamp ]) self . d [ timestamp ] = price self . ls . add ( price ) self . last = max ( self . last , timestamp ) def current ( self ) -> int : return self . d [ self . last ] def maximum ( self ) -> int : return self . ls [ - 1 ] def minimum ( self ) -> int : return self . ls [ 0 ] # Your StockPrice object will be instantiated and called as such: # obj = StockPrice() # obj.update(timestamp,price) # param_2 = obj.current() # param_3 = obj.maximum() # param_4 = obj.minimum()Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.