# Stock Price Fluctuation **Difficulty:** MEDIUM [External](https://leetcode.com/problems/stock-price-fluctuation) Canonical: https://scaleengineer.com/dsa/problems/stock-price-fluctuation **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Data Stream](https://scaleengineer.com/dsa/patterns/data-stream) **Data structures:** Hash Table, Heap (Priority Queue), Ordered Set **Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [MongoDB](https://scaleengineer.com/companies/mongodb), [Ripple](https://scaleengineer.com/companies/ripple), [Mixpanel](https://scaleengineer.com/companies/mixpanel) --- ## Problem 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 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 <= 109` * At most `105` 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**. # Approaches ## Brute Force using HashMap 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. **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`. **Pros:** Very simple to understand and implement.; The `update` operation is highly efficient with an average time complexity of O(1). **Cons:** The `current()`, `maximum()`, and `minimum()` 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. ### Explanation In this straightforward approach, we use a `HashMap` 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 the `HashMap`. 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 the `HashMap` to 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 the `HashMap` and 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. ```java class StockPrice { HashMap 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; } } ``` ### Algorithm - Initialize a `HashMap` to store timestamp-price records. - For `update(timestamp, price)`, simply use `map.put(timestamp, price)`. - For `current()`, iterate through all keys in the `HashMap` to find the maximum timestamp, then retrieve its price. This takes O(N) time. - For `maximum()`, iterate through all values in the `HashMap` to find the maximum price. This takes O(N) time. - For `minimum()`, iterate through all values in the `HashMap` to find the minimum price. This also takes O(N) time. ## Optimized `current()` using TreeMap 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. **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`. **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()` and `minimum()` operations remain inefficient with O(N) time complexity.; The `update` operation is slightly slower (O(log N)) than the pure `HashMap` approach (O(1)). ### Explanation By replacing the `HashMap` with a `TreeMap`, 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 the `TreeMap`. This operation takes O(log N) time, as the map needs to maintain its sorted order. - **`current()`**: Since the `TreeMap` is sorted by timestamp, the latest timestamp is simply the last key in the map. We can retrieve this using `records.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 the `TreeMap`. This remains an O(N) operation. - **`minimum()`**: Similarly, finding the minimum price requires iterating through all values, taking O(N) time. ```java class StockPrice { TreeMap 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; } } ``` ### Algorithm - Initialize a `TreeMap` to store timestamp-price records, which keeps them sorted by timestamp. - For `update(timestamp, price)`, use `map.put(timestamp, price)`. This takes O(log N) time. - For `current()`, retrieve the last key (the maximum timestamp) from the `TreeMap` using `lastKey()` and get its value. This takes O(log N) time. - For `maximum()` and `minimum()`, iterate through all values in the `TreeMap`, which still takes O(N) time. ## Efficient Approach with Two TreeMaps 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. **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`. **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 `TreeMap`s. ### Explanation To achieve optimal performance for all operations, we use two `TreeMap`s: 1. `TreeMap timestampToPrice`: This maps timestamps to their prices. Being sorted by timestamp, it allows us to find the `current` price in O(log N) time. 2. `TreeMap priceToCount`: This maps prices to their frequencies (how many times each price appears). Being sorted by price, it allows us to find the `minimum` and `maximum` prices 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 from `timestampToPrice`. We then decrement the count of this old price in `priceToCount`. If the count drops to zero, we remove the price from `priceToCount`. After handling the old price, we update `timestampToPrice` with the new price and increment the new price's count in `priceToCount`. - **`current()`**: The latest price corresponds to the highest timestamp, which is the last key in `timestampToPrice`. This is an O(log N) operation. - **`maximum()`**: The maximum price is the highest price recorded, which is the last key in `priceToCount`. This is an O(log P) operation. - **`minimum()`**: The minimum price is the lowest price recorded, which is the first key in `priceToCount`. This is an O(log P) operation. ```java class StockPrice { // Stores timestamp -> price, sorted by timestamp private TreeMap timestampToPrice; // Stores price -> count of that price, sorted by price private TreeMap 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(); } } ``` ### Algorithm - Use two `TreeMap`s: `timestampToPrice` to map timestamps to prices, and `priceToCount` to map prices to their frequencies. - For `update(timestamp, price)`: - If the timestamp exists, find the `oldPrice`, and decrement its count in `priceToCount`. If the count becomes zero, remove the `oldPrice` entry. - Update `timestampToPrice` with the new price. - Increment the count of the new `price` in `priceToCount`. - For `current()`: Get the last key from `timestampToPrice` and return its value. - For `maximum()`: Return the last key from `priceToCount`. - For `minimum()`: Return the first key from `priceToCount`. # Solutions ### Java ```java 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(); */ ``` ### CPP ```cpp 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(); */ ``` ### Python ```python 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() ```