2034. Stock Price Fluctuation
Problem Description
In this problem, you are tasked with designing an algorithm to maintain a record of stock prices that come in a stream. Each record includes two pieces of information: a timestamp and the stock's price at that timestamp. The key challenges in this problem are:
- The stock price records do not arrive in chronological order.
- Some records may be incorrect and could be corrected by later records with the same timestamp.
Your algorithm should be able to handle these issues and provide four functionalities:
- Update the stock price at a given timestamp with the correct price.
- Get the latest price of the stock, which is the price at the most recent timestamp.
- Find the maximum price that the stock has reached based on the records.
- Find the minimum price that the stock has been at based on the records.
To achieve these objectives, your implementation should provide the following methods:
StockPrice()
: Constructor for the class that initializes an empty set of price records.update(timestamp, price)
: Method to update the price of the stock at the given timestamp.current()
: Method that returns the latest price of the stock.maximum()
: Method that returns the maximum price of the stock.minimum()
: Method that returns the minimum price of the stock.
The main challenges to tackle in the problem are ensuring that the correct price is represented in the records, even when updates occur out of order, and performing the minimization and maximization operations efficiently.
Intuition
The problem requires us to efficiently perform updates and queries on a dataset with irregular updates and corrections. To handle updates, we must be able to overwrite existing prices at specific timestamps. Therefore, we use a hash table to map timestamps to prices, providing us with constant-time access and updates for individual records.
However, we must also efficiently find the maximum and minimum stock prices. An unsorted array or list would require linear-time searches to find these values, which would not be efficient enough as the number of records grows. Therefore, we rely on a data structure that maintains the prices in sorted order.
We use an ordered set (or in the case of the reference solution with Python, a SortedList
) to keep the prices sorted at all times. When we update a price at a given timestamp, we remove the old price from the SortedList
if it exists, and add the new price. This enables us to always have the minimum and maximum prices at the ends of the SortedList
, allowing us to query them in O(1) time.
The last
variable is updated with each call to update
to ensure we can always provide the latest price of the stock. We take the maximum timestamp we've seen to ensure last
always correctly reflects the latest timestamp.
With this approach, every update operation takes time because we might need to remove an old price and add a new one to the SortedList
. Meanwhile, querying the latest price takes time, as we just need to look up the price at the last timestamp. Finding the maximum and minimum is also because SortedList
maintains the order of prices, so the first and last elements are the minimum and maximum, respectively.
Overall, this algorithm is efficient and handles the challenges posed by the unordered and potentially incorrect stream of stock price records.
Learn more about Data Stream and Heap (Priority Queue) patterns.
Solution Approach
The implementation of the solution involves several steps corresponding to the different functionalities our StockPrice
class must support. We use specific algorithms and data structures to achieve the necessary efficiency.
Here's a breakdown of each method in the StockPrice
class and the rationale behind them:
-
StockPrice()
: This is the constructor for our class. We initialize a hash tableself.d
to keep the price records with timestamps as keys. This allows us to quickly access and update the price for any given timestamp. We also initialize aSortedList
calledself.ls
to maintain the prices in sorted order, enabling us to get the min and max prices quickly. Lastly, we initializeself.last
as 0 to keep track of the most recent timestamp. -
update(timestamp, price)
: For each update to the stock price, we first check if the timestamp already exists in our hash table. If it does, we find the corresponding old price in ourSortedList
and remove it because it needs to be corrected. We then update the hash table with the new price at the given timestamp. After that, we add the new price to theSortedList
. This ensures that our sorted list always contains the correct, up-to-date prices and can give us the min and max when needed. The use of aSortedList
allows both removal and addition operations to be conducted inO(log n)
time. Finally, we updateself.last
to be the maximum of itself and the current timestamp, ensuring thatself.last
always refers to the latest time. -
current()
: This method simply returns the price associated with the latest timestamp,self.last
. Since we've been updatingself.last
with every call toupdate
, we know thatself.d[self.last]
will give us the current price. This operation isO(1)
as it's a direct hash map access. -
maximum()
: To get the maximum price of the stock at any time, we take advantage of the properties of theSortedList
. Sinceself.ls
maintains the order of elements, the last element (obtained byself.ls[-1]
) is the maximum price. The time complexity of getting the last element from aSortedList
isO(1)
. -
minimum()
: Similarly to getting the maximum price, we useself.ls[0]
to get the minimum price, which is the first element in our sorted list. This operation is alsoO(1)
.
The reference implementation provided efficiently balances the need to update prices for any timestamp quickly and to retrieve the minimum and maximum prices without having to sort the prices or scan the entire price list with each query.
Overall, the use of a hash table allows us to deal with the unordered nature of updates and potential corrections, while the SortedList
maintains a running order of prices that facilitates efficient retrieval of minimum and maximum values.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach with a hypothetical StockPrice
class.
Initially, we create our StockPrice
class instance. There are no records yet, so all internal structures are empty.
stock_prices = StockPrice()
Now, let's start streaming in some stock price updates:
- We receive an update with
(timestamp=4, price=150)
. Since this is the first record, we add it to both the hash table and theSortedList
, and setself.last
to 4.
stock_prices.update(4, 150) # self.d = {4: 150} # self.ls = [150] # self.last = 4
- The second update comes with
(timestamp=2, price=100)
. It's out of order, but with our hash map, we can handle it. We add the record to the hash table andSortedList
.self.last
remains 4 as this timestamp is older.
stock_prices.update(2, 100) # self.d = {4: 150, 2: 100} # self.ls = [100, 150] # self.last = 4
- Now we receive a correction for timestamp 4; the new price is 175
(timestamp=4, price=175)
. We update the price in the hash table for timestamp 4 and adjust theSortedList
by removing the old price and adding the new one. Our last timestamp is still 4.
stock_prices.update(4, 175) # self.d = {4: 175, 2: 100} # self.ls = [100, 175] # self.last = 4
- A new update arrives with
(timestamp=5, price=200)
. We add this new price and updateself.last
to 5 since this is the latest timestamp we've seen.
stock_prices.update(5, 200) # self.d = {4: 175, 2: 100, 5: 200} # self.ls = [100, 175, 200] # self.last = 5
Given the above sequence of events, let's use our methods to answer some queries:
current()
: Calling this method will return the latest price, which is the price at the latest timestamp,self.last
, which points to timestamp 5.
current_price = stock_prices.current() # Returns: 200
maximum()
: This method will give us the maximum price encountered in the stock records.
max_price = stock_prices.maximum() # Returns: 200
minimum()
: This will give us the minimum price seen in the records.
min_price = stock_prices.minimum() # Returns: 100
This example walk-through shows how the class implementation handles out-of-order updates and corrections while still being able to efficiently query the current, minimum, and maximum prices.
Solution Implementation
1from sortedcontainers import SortedList
2
3class StockPrice:
4 def __init__(self):
5 self.prices_by_timestamp = {} # Dictionary to store price by timestamp
6 self.sorted_prices = SortedList() # SortedList to keep prices sorted
7 self.latest_timestamp = 0 # Variable to store the last timestamp
8
9 def update(self, timestamp: int, price: int) -> None:
10 # If the price at the given timestamp is already in the dictionary,
11 # remove the previous price from the sorted list.
12 if timestamp in self.prices_by_timestamp:
13 old_price = self.prices_by_timestamp[timestamp]
14 self.sorted_prices.remove(old_price)
15 # Update the dictionary with the new price and add the price to the sorted list.
16 self.prices_by_timestamp[timestamp] = price
17 self.sorted_prices.add(price)
18 # Update the latest timestamp if the new one is later.
19 self.latest_timestamp = max(self.latest_timestamp, timestamp)
20
21 def current(self) -> int:
22 # Return the latest price at the latest timestamp.
23 return self.prices_by_timestamp[self.latest_timestamp]
24
25 def maximum(self) -> int:
26 # Return the maximum price in the sorted list.
27 return self.sorted_prices[-1]
28
29 def minimum(self) -> int:
30 # Return the minimum price in the sorted list.
31 return self.sorted_prices[0]
32
33
34# Example:
35# stock_price_tracker = StockPrice()
36# stock_price_tracker.update(1, 10)
37# current_price = stock_price_tracker.current()
38# max_price = stock_price_tracker.maximum()
39# min_price = stock_price_tracker.minimum()
40
1import java.util.HashMap;
2import java.util.Map;
3import java.util.TreeMap;
4
5class StockPrice {
6 // HashMap for storing timestamp and respective price.
7 private Map<Integer, Integer> timestampToPriceMap = new HashMap<>();
8
9 // TreeMap for keeping track of the number of instances of a price level.
10 private TreeMap<Integer, Integer> priceFrequencyMap = new TreeMap<>();
11
12 // Variable to store the last timestamp processed.
13 private int latestTimestamp;
14
15 // Constructor
16 public StockPrice() {}
17
18 // Updates the price of the stock at the given timestamp
19 public void update(int timestamp, int price) {
20 // If the timestamp already exists, update the frequency of the old price
21 if (timestampToPriceMap.containsKey(timestamp)) {
22 int oldPrice = timestampToPriceMap.get(timestamp);
23 // Decrease the frequency of the old price; if it reaches 0, remove it from the TreeMap
24 if (priceFrequencyMap.merge(oldPrice, -1, Integer::sum) == 0) {
25 priceFrequencyMap.remove(oldPrice);
26 }
27 }
28
29 // Update the timestamp to map to the new price
30 timestampToPriceMap.put(timestamp, price);
31 // Increase the frequency of the new price, adding it if it's not already present
32 priceFrequencyMap.merge(price, 1, Integer::sum);
33 // Update the latest timestamp to the current one if it's the latest
34 latestTimestamp = Math.max(latestTimestamp, timestamp);
35 }
36
37 // Gets the latest price of the stock
38 public int current() {
39 return timestampToPriceMap.get(latestTimestamp);
40 }
41
42 // Returns the maximum stock price recorded so far
43 public int maximum() {
44 return priceFrequencyMap.lastKey();
45 }
46
47 // Returns the minimum stock price recorded so far
48 public int minimum() {
49 return priceFrequencyMap.firstKey();
50 }
51}
52
53/* Usage:
54 * StockPrice obj = new StockPrice();
55 * obj.update(timestamp, price);
56 * int currentPrice = obj.current();
57 * int maxPrice = obj.maximum();
58 * int minPrice = obj.minimum();
59 */
60
1#include <unordered_map>
2#include <set>
3
4class StockPrice {
5public:
6 // Constructor
7 StockPrice() {
8 }
9
10 // Updates the price of the stock at the given timestamp
11 void update(int timestamp, int price) {
12 // If the timestamp already exists, remove the old price from the multiset
13 if (timestampToPrice.count(timestamp)) {
14 prices.erase(prices.find(timestampToPrice[timestamp]));
15 }
16 // Update the timestamp to price mapping
17 timestampToPrice[timestamp] = price;
18 // Insert the new price into the multiset
19 prices.insert(price);
20 // Update the latest timestamp
21 latestTimestamp = std::max(latestTimestamp, timestamp);
22 }
23
24 // Retrieves the current price of the stock
25 int current() {
26 return timestampToPrice[latestTimestamp];
27 }
28
29 // Retrieves the maximum price of the stock
30 int maximum() {
31 // The last element in a multiset is the largest
32 return *prices.rbegin();
33 }
34
35 // Retrieves the minimum price of the stock
36 int minimum() {
37 // The first element in a multiset is the smallest
38 return *prices.begin();
39 }
40
41private:
42 // Mapping from timestamp to price
43 std::unordered_map<int, int> timestampToPrice;
44 // A multiset to keep prices sorted to get min and max efficiently
45 std::multiset<int> prices;
46 // Storing the latest timestamp
47 int latestTimestamp = 0;
48};
49
50/**
51 * Your StockPrice object will be instantiated and called as such:
52 * StockPrice* obj = new StockPrice();
53 * obj->update(timestamp, price);
54 * int param_2 = obj->current();
55 * int param_3 = obj->maximum();
56 * int param_4 = obj->minimum();
57 */
58
1// Global variables to replace class members
2let timestampToPrice: Record<number, number> = {};
3let prices: Set<number> = new Set();
4let latestTimestamp: number = 0;
5
6// Updates the price of the stock at the given timestamp
7function update(timestamp: number, price: number): void {
8 // If the timestamp already exists, remove the old price from the prices set
9 if (timestampToPrice.hasOwnProperty(timestamp)) {
10 prices.delete(timestampToPrice[timestamp]);
11 }
12
13 // Update the mapping from timestamp to price
14 timestampToPrice[timestamp] = price;
15
16 // Add the new price to the prices set
17 prices.add(price);
18
19 // Update the latest timestamp if the new timestamp is more recent
20 latestTimestamp = Math.max(latestTimestamp, timestamp);
21}
22
23// Retrieves the current price of the stock
24function current(): number {
25 return timestampToPrice[latestTimestamp];
26}
27
28// Retrieves the maximum price of the stock
29function maximum(): number {
30 // Convert the set to an array to easily access the max value
31 return Math.max(...Array.from(prices));
32}
33
34// Retrieves the minimum price of the stock
35function minimum(): number {
36 // Convert the set to an array to easily access the min value
37 return Math.min(...Array.from(prices));
38}
39
Time and Space Complexity
Time Complexity
-
__init__
: Initializing the StockPrice object involves setting up an empty dictionary (self.d
), a SortedList (self.ls
), and an integer (self.last
). The time complexity for this isO(1)
because it's just some variable assignments. -
update
: This method may involve both removing an old price and adding a new one to the sorted list. Removing from a SortedList has a time complexity ofO(log n)
wheren
is the number of unique timestamps, and adding to the SortedList also has a time complexity ofO(log n)
. Therefore, the total time complexity forupdate
isO(log n)
for the sorted list operations. Updating the dictionary and last timestamp takes constant time,O(1)
. -
current
: Fetching the current price is a dictionary lookup, which isO(1)
. -
maximum
: Getting the maximum price is anO(1)
operation since the SortedList maintains its elements in a sorted order, and getting the last element (max) doesn't require any traversal. -
minimum
: Similar tomaximum
, getting the minimum price is anO(1)
operation because it involves fetching the first element of the SortedList.
Space Complexity
- The space complexity is
O(n)
wheren
is the number ofupdate
operations, which correlates directly to the number of unique elements stored in the dictionary and the SortedList. Each uniqueupdate
call potentially adds one new entry to the dictionary and one new entry to the SortedList (unless a previous price is being overridden, in which case the new price replaces the old in the dictionary, but the SortedList may still grow if the price is a new value not already in the list).
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!