Problem Description

You need to design a system that tracks stock prices over time. The challenge is that price records arrive out of order, and some records might be incorrect and need to be corrected later.

The system receives a stream of records, where each record contains:

• A timestamp (when the price was recorded)
• A price (the stock price at that timestamp)

Key challenges:

• Records don't arrive in chronological order
• A record with the same timestamp might appear later to correct an earlier wrong price

Your StockPrice class must support these operations:

1. StockPrice(): Initialize an empty price tracking system

2. update(timestamp, price): Record or correct the price at a given timestamp

   • If this timestamp already exists, replace the old price with the new one
   • If it's a new timestamp, add it to the records

3. current(): Return the price at the most recent timestamp

   • This means the price with the largest timestamp value, not the most recently added record

4. maximum(): Return the highest price across all timestamps in the current records

5. minimum(): Return the lowest price across all timestamps in the current records

For example, if you receive updates for timestamps [10, 5, 15] with prices [100, 90, 110], the current price would be 110 (price at timestamp 15), even though timestamp 5 was added after timestamp 10. If you later update timestamp 15 with price 95, the current price becomes 95, and the maximum price changes from 110 to 100.

Intuition

To solve this problem, let's think about what we need to track and what operations we need to support efficiently.

First, we need to handle price updates and corrections. Since a timestamp can be updated multiple times (corrections), we need a way to map each timestamp to its current price. A hash table (d) is perfect for this - it gives us O(1) lookup and update for any timestamp.

For finding the current price, we need to know which timestamp is the latest. We could scan through all timestamps each time, but that's inefficient. Instead, we can maintain a variable (last) that tracks the maximum timestamp seen so far. Whenever we update a timestamp, we check if it's larger than our current last and update accordingly.

The tricky part is maintaining the maximum and minimum prices efficiently. Here's the challenge: when we update a timestamp that already exists, we're replacing an old price with a new one. This means:

• The old price should no longer be considered for max/min calculations
• The new price should be added to our consideration

If we just kept track of the single max and min values, we'd have a problem when updating. For instance, if the current maximum price gets corrected to a lower value, what's the new maximum? We'd have to scan through all prices to find it.

This is where an ordered data structure comes in. By maintaining all current prices in a sorted order (ls - a SortedList), we can:

• Always get the minimum price from the first element (ls[0])
• Always get the maximum price from the last element (ls[-1])
• When updating an existing timestamp, remove the old price from the sorted list and add the new one

The SortedList maintains the sorted order automatically, giving us O(log n) operations for adding and removing elements, while providing O(1) access to the minimum and maximum values.

This approach elegantly handles all requirements: corrections are handled by the hash table, the latest timestamp is tracked separately, and the sorted list maintains our ability to quickly find extremes even as prices change.

Learn more about Data Stream and Heap (Priority Queue) patterns.

Solution Approach

Let's implement the solution using a hash table and an ordered set (SortedList in Python).

Data Structures:

• d: A hash table (dictionary) that maps timestamp → price. This allows us to quickly look up or update the price at any timestamp.
• ls: A SortedList that maintains all current prices in sorted order. This enables efficient access to minimum and maximum prices.
• last: An integer tracking the maximum timestamp seen so far, which represents the "latest" time.

Implementation Details:

1. __init__(): Initialize empty data structures

   • Create an empty dictionary d
   • Create an empty SortedList ls
   • Set last = 0 (no timestamps seen yet)

2. update(timestamp, price): Handle new prices or corrections

   • First, check if this timestamp already exists in d
   • If it exists (this is a correction):
     • Remove the old price from ls using ls.remove(d[timestamp])
     • This ensures the old incorrect price won't affect our min/max calculations
   • Update the hash table: d[timestamp] = price
   • Add the new price to the sorted list: ls.add(price)
   • Update the latest timestamp: last = max(last, timestamp)
   • Time Complexity: O(log n) due to SortedList operations

3. current(): Return the price at the latest timestamp

   • Simply return d[self.last]
   • Since we maintain last as the maximum timestamp, this gives us the most recent price
   • Time Complexity: O(1)

4. maximum(): Return the highest price

   • Return ls[-1] (the last element in the sorted list)
   • Since ls maintains prices in sorted order, the last element is always the maximum
   • Time Complexity: O(1) for access (though the overall complexity is O(log n) when considering the updates that maintain the structure)

5. minimum(): Return the lowest price

   • Return ls[0] (the first element in the sorted list)
   • The first element in a sorted list is always the minimum
   • Time Complexity: O(1) for access

Why This Works:

• The hash table handles the timestamp → price mapping, allowing efficient updates and lookups
• The SortedList automatically maintains all current prices in order, so we always know the min and max
• When a price is corrected, we remove the old value from the sorted list and add the new one, ensuring our min/max queries remain accurate
• The last variable eliminates the need to search for the maximum timestamp every time we need the current price

This design ensures all operations are efficient while correctly handling out-of-order updates and price corrections.

Example Walkthrough

Let's walk through a sequence of operations to see how our solution handles updates, corrections, and queries:

Initial State:

• d = {} (empty dictionary)
• ls = [] (empty sorted list)
• last = 0 (no timestamps yet)

Operation 1: update(10, 100)

• Timestamp 10 doesn't exist in d, so this is a new entry
• Add to dictionary: d = {10: 100}
• Add to sorted list: ls = [100]
• Update last: last = max(0, 10) = 10

Operation 2: update(5, 90)

• Timestamp 5 doesn't exist in d, so this is a new entry
• Add to dictionary: d = {10: 100, 5: 90}
• Add to sorted list: ls = [90, 100] (automatically sorted)
• Update last: last = max(10, 5) = 10 (stays at 10)

Operation 3: current()

• Return d[last] = d[10] = 100
• Note: Even though timestamp 5 was added more recently, timestamp 10 is the latest chronologically

Operation 4: update(15, 110)

• Timestamp 15 doesn't exist in d, so this is a new entry
• Add to dictionary: d = {10: 100, 5: 90, 15: 110}
• Add to sorted list: ls = [90, 100, 110]
• Update last: last = max(10, 15) = 15

Operation 5: maximum()

• Return ls[-1] = 110 (last element of sorted list)

Operation 6: minimum()

• Return ls[0] = 90 (first element of sorted list)

Operation 7: update(15, 95) (Correction!)

• Timestamp 15 exists in d with price 110
• Remove old price from sorted list: ls.remove(110) → ls = [90, 100]
• Update dictionary: d = {10: 100, 5: 90, 15: 95}
• Add new price to sorted list: ls.add(95) → ls = [90, 95, 100]
• Update last: last = max(15, 15) = 15 (stays at 15)

Operation 8: current()

• Return d[last] = d[15] = 95
• The corrected price is now returned

Operation 9: maximum()

• Return ls[-1] = 100
• Note: The maximum changed from 110 to 100 after the correction

This example demonstrates how:

• The system handles out-of-order timestamps (5 added after 10)
• Price corrections are properly reflected (timestamp 15 updated from 110 to 95)
• The sorted list maintains accurate min/max values even after corrections
• The current() method always returns the price at the chronologically latest timestamp, not the most recently added one

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1) - Simple initialization of data structures
• update(timestamp, price): O(log n) - The dictionary lookup/update is O(1), but SortedList.remove() and SortedList.add() operations each take O(log n) time where n is the number of unique timestamps
• current(): O(1) - Direct dictionary lookup using the last timestamp
• maximum(): O(1) - Direct access to the last element in the sorted list
• minimum(): O(1) - Direct access to the first element in the sorted list

Space Complexity: O(n) where n is the number of unique timestamps (update operations). This is because:

• The dictionary self.d stores at most n timestamp-price pairs
• The SortedList self.ls maintains at most n prices (one for each unique timestamp)
• Even though updates to existing timestamps replace old prices rather than accumulating them, the space is still bounded by the number of unique timestamps

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Price Corrections Properly

The Pitfall: A critical mistake is forgetting to remove the old price from the sorted list when updating an existing timestamp. If you only add the new price without removing the old one, the sorted list will contain both prices, leading to incorrect minimum/maximum values.

Incorrect Implementation:

def update(self, timestamp: int, price: int) -> None:
    # WRONG: Only adding new price without removing old one
    self.timestamp_to_price[timestamp] = price
    self.sorted_prices.add(price)
    self.latest_timestamp = max(self.latest_timestamp, timestamp)

Why It Fails: If timestamp 10 initially has price 100, and later gets corrected to 50:

• The sorted list would contain both [50, 100]
• maximum() would incorrectly return 100 (which no longer exists)
• The sorted list grows unnecessarily with phantom prices

The Solution: Always check if a timestamp exists and remove its old price before adding the new one:

def update(self, timestamp: int, price: int) -> None:
    if timestamp in self.timestamp_to_price:
        old_price = self.timestamp_to_price[timestamp]
        self.sorted_prices.remove(old_price)  # Critical step!
  
    self.timestamp_to_price[timestamp] = price
    self.sorted_prices.add(price)
    self.latest_timestamp = max(self.latest_timestamp, timestamp)

2. Using a Regular List Instead of SortedList

The Pitfall: Using a standard Python list and manually sorting it after each update, or using binary search for insertions.

Incorrect Implementation:

def __init__(self):
    self.sorted_prices = []  # Regular list

def update(self, timestamp: int, price: int) -> None:
    # ... handle timestamp updates ...
    self.sorted_prices.append(price)
    self.sorted_prices.sort()  # O(n log n) every time!

Why It Fails:

• Sorting after each insertion is O(n log n), making updates extremely inefficient
• Manual binary search insertion is error-prone and still O(n) due to list shifting
• Removing elements requires linear search O(n) plus shifting O(n)

The Solution: Use a proper self-balancing data structure like SortedList from sortedcontainers, which maintains sorted order with O(log n) operations for add/remove.

3. Confusing "Current" with "Most Recently Added"

The Pitfall: Tracking the most recently added record instead of the record with the maximum timestamp.

Incorrect Implementation:

def __init__(self):
    self.last_added_timestamp = None  # WRONG concept

def update(self, timestamp: int, price: int) -> None:
    # ... other update logic ...
    self.last_added_timestamp = timestamp  # WRONG: tracks insertion order

def current(self) -> int:
    return self.timestamp_to_price[self.last_added_timestamp]  # Returns wrong price

Why It Fails: If updates arrive as: timestamp 100 → timestamp 50 → timestamp 75

• The "current" price should be at timestamp 100 (largest timestamp)
• But this would return the price at timestamp 75 (last added)

The Solution: Always track the maximum timestamp seen, not the order of insertion:

self.latest_timestamp = max(self.latest_timestamp, timestamp)

4. Handling Duplicate Prices Incorrectly

The Pitfall: Not considering that multiple timestamps might have the same price value, leading to removal of wrong prices.

Scenario That Could Fail:

• Timestamp 10 has price 100
• Timestamp 20 has price 100 (same price, different timestamp)
• Update timestamp 10 to price 50
• If using a set or not careful with removal, might remove the wrong instance of 100

The Solution: SortedList handles duplicates correctly - remove() only removes one instance of the value. This is why the current implementation works correctly even with duplicate prices.