LeetCode Solutions Blog

Stock Price Fluctuation

Number: 2161

Difficulty: Medium

Paid? No

Problem Description

Design a StockPrice class that processes a stream of stock price records (each consisting of a timestamp and a price). Records may arrive out of order and even update previously seen timestamps with corrected prices. Implement methods to update the price for a given timestamp, return the latest price (i.e. the price corresponding to the greatest timestamp), and efficiently query for the maximum and minimum prices based on the current records.

Key Insights

Use a hash table (or dictionary) to map each timestamp to its latest price.
Maintain two heaps (a max heap and a min heap) to quickly retrieve the maximum and minimum prices.
Since updates can change historical prices, use lazy deletion in the heaps: when the top element does not match the current price in the hash table, repeatedly pop it.
Track the latest timestamp separately to efficiently return the current/latest price.

Space and Time Complexity

Time Complexity:

update: O(log n) due to pushing into two heaps.
current: O(1).
maximum/minimum: O(log n) in the worst-case (when cleaning outdated heap entries).

Space Complexity:

O(n) to store the hash table and both heaps.

Solution

We use a hash table (or dictionary) to store the mapping from timestamp to price. For maximum and minimum queries, we use a max heap (storing negative prices for a max-oriented comparison) and a min heap. When updating a timestamp, we update the hash table and push the new (price, timestamp) pair into both heaps. For queries, we repeatedly check the top of the heap and compare with the hash table – if it is outdated (i.e. the hash table’s price for the timestamp does not match the heap entry), we pop the invalid entry until we find a valid one. We keep track of the latest timestamp in a variable so that the current price query is efficient.

Code Solutions

# Python solution
import heapq

class StockPrice:
    def __init__(self):
        # Dictionary mapping timestamp to price
        self.price_by_timestamp = {}
        # Track the latest timestamp seen so far
        self.latest_timestamp = 0
        # Min heap to obtain the minimum price quickly; stores (price, timestamp)
        self.min_heap = []
        # Max heap to obtain the maximum price quickly; stores (-price, timestamp)
        self.max_heap = []

    def update(self, timestamp: int, price: int) -> None:
        # Update the dictionary with the new price for the given timestamp
        self.price_by_timestamp[timestamp] = price
        # Update the latest timestamp if necessary
        self.latest_timestamp = max(self.latest_timestamp, timestamp)
        # Push the new price with its timestamp into the min heap
        heapq.heappush(self.min_heap, (price, timestamp))
        # Push the negative of price to simulate a max heap into the max heap
        heapq.heappush(self.max_heap, (-price, timestamp))

    def current(self) -> int:
        # Return the price corresponding to the latest timestamp
        return self.price_by_timestamp[self.latest_timestamp]

    def maximum(self) -> int:
        # Remove outdated entries from the max heap
        while self.max_heap:
            # Get the price (as negative) and associated timestamp from the top of the heap
            neg_price, timestamp = self.max_heap[0]
            # If the price in the dictionary doesn't match the current heap entry, it's outdated
            if self.price_by_timestamp[timestamp] != -neg_price:
                heapq.heappop(self.max_heap)
            else:
                return -neg_price
        return -1  # Edge case (should not occur as current is called after an update)

    def minimum(self) -> int:
        # Remove outdated entries from the min heap
        while self.min_heap:
            price, timestamp = self.min_heap[0]
            # If the price in the dictionary doesn't match, pop it as it's outdated
            if self.price_by_timestamp[timestamp] != price:
                heapq.heappop(self.min_heap)
            else:
                return price
        return -1  # Edge case (should not occur as current is called after an update)