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:

1. The stock price records do not arrive in chronological order.
2. 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 $O(\log n)$ time because we might need to remove an old price and add a new one to the SortedList. Meanwhile, querying the latest price takes $O(1)$ time, as we just need to look up the price at the last timestamp. Finding the maximum and minimum is also $O(1)$ 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 table self.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 a SortedList called self.ls to maintain the prices in sorted order, enabling us to get the min and max prices quickly. Lastly, we initialize self.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 our SortedList 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 the SortedList. 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 a SortedList allows both removal and addition operations to be conducted in O(log n) time. Finally, we update self.last to be the maximum of itself and the current timestamp, ensuring that self.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 updating self.last with every call to update, we know that self.d[self.last] will give us the current price. This operation is O(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 the SortedList. Since self.ls maintains the order of elements, the last element (obtained by self.ls[-1]) is the maximum price. The time complexity of getting the last element from a SortedList is O(1).

• minimum(): Similarly to getting the maximum price, we use self.ls[0] to get the minimum price, which is the first element in our sorted list. This operation is also O(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.

Example 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:

1. We receive an update with (timestamp=4, price=150). Since this is the first record, we add it to both the hash table and the SortedList, and set self.last to 4.

stock_prices.update(4, 150)
# self.d = {4: 150}
# self.ls = [150]
# self.last = 4

2. 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 and SortedList. 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

3. 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 the SortedList 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

4. A new update arrives with (timestamp=5, price=200). We add this new price and update self.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

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 is O(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 of O(log n) where n is the number of unique timestamps, and adding to the SortedList also has a time complexity of O(log n). Therefore, the total time complexity for update is O(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 is O(1).

• maximum: Getting the maximum price is an O(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 to maximum, getting the minimum price is an O(1) operation because it involves fetching the first element of the SortedList.

Space Complexity

• The space complexity is O(n) where n is the number of update operations, which correlates directly to the number of unique elements stored in the dictionary and the SortedList. Each unique update 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.