Stock Price Fluctuation
Problem Description
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
Constraints:
- 1 <= timestamp, price <= 109
- At most 105 calls will be made in total to
update,current,maximum, andminimum. current,maximum, andminimumwill be called only afterupdatehas been called at least once.
Solve it on LeetCode
Approaches
1. Brute Force with List
Intuition:
The brute force approach is fairly straightforward. We maintain a list of pairs and simply update or query the list as required. This approach will straightforwardly tackle the problem but will have inefficiencies especially given the constraints.
Code:
Complexity Analysis:
- Time Complexity:
update: O(n) where n is the number of prices, as we might need to traverse the entire list to update a price.current: O(n) to find the current price matching the maximum timestamp.maximumandminimum: O(n) each to find the maximum and minimum prices.- Space Complexity: O(n) since we store up to n timestamps and prices.
2. Using HashMap for Tracking Prices
Intuition:
Using a HashMap allows for more efficient updates. By keeping track of the prices with their timestamps in a map, the update and current operations become more efficient. However, we still need list-like structures to calculate max and min in a straightforward method or employ further structures to maintain these values efficiently.
Code:
- Time Complexity:
updateandcurrent: O(1) due to HashMap operations.maximumandminimum: O(n) because we still have to possibly traverse all prices.- Space Complexity: O(n) for storing n entries in the map.
3. Using TreeMap for Efficient Ordering
Intuition:
TreeMap inherently sorts its keys, providing a way to efficiently find min and max along with an easy way to get the current price using the highest timestamp. This allows all operations to be more efficient except adding or removing, which are logarithmic due to the properties of the TreeMap.
Code:
- Time Complexity:
update: O(log n) for both adding the new timestamp-price pair and updating counting in thecountmap.current: O(1) using TreeMap's floor function.maximumandminimum: O(1) to directly access the max and min keys in thecountTreeMap.- Space Complexity: O(n) as we store prices and counts for up to n different timestamps.