2034. Stock Price Fluctuation

MediumDesignHash TableData StreamOrdered SetHeap (Priority Queue)
Leetcode Link

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(logn)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)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)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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

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.

1stock_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.
1stock_prices.update(4, 150)
2# self.d = {4: 150}
3# self.ls = [150]
4# self.last = 4
  1. 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.
1stock_prices.update(2, 100)
2# self.d = {4: 150, 2: 100}
3# self.ls = [100, 150]
4# self.last = 4
  1. 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.
1stock_prices.update(4, 175)
2# self.d = {4: 175, 2: 100}
3# self.ls = [100, 175]
4# self.last = 4
  1. 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.
1stock_prices.update(5, 200)
2# self.d = {4: 175, 2: 100, 5: 200}
3# self.ls = [100, 175, 200]
4# 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.
1current_price = stock_prices.current()
2# Returns: 200
  • maximum(): This method will give us the maximum price encountered in the stock records.
1max_price = stock_prices.maximum()
2# Returns: 200
  • minimum(): This will give us the minimum price seen in the records.
1min_price = stock_prices.minimum()
2# 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 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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄