LeetCode Solutions Blog

Stock Price Fluctuation

Difficulty: Medium

Problem Description

You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp. Due to the volatile nature of the stock market, the records may not come in order, and some records may be incorrect. Your task is to design an algorithm that updates the price of the stock at a particular timestamp, finds the latest price, maximum price, and minimum price based on the current records.

Key Insights

Use a hash table to store the latest price for each timestamp.
Maintain a separate structure to keep track of the maximum and minimum prices efficiently.
Ensure that the latest price is always retrievable by storing the latest timestamp.
Correct updates to prices must adjust the maximum and minimum if needed.

Space and Time Complexity

Time Complexity:

update: O(log n) for maintaining max and min heaps
current: O(1)
maximum: O(1)
minimum: O(1)

Space Complexity: O(n) where n is the number of unique timestamps.

Solution

To solve this problem, we can use a hash table (dictionary) to store the prices associated with each timestamp. A max-heap and min-heap can be utilized to efficiently track the maximum and minimum prices. When an update occurs, we adjust the price in the hash table and update the heaps accordingly. This allows us to quickly retrieve the latest price, maximum price, and minimum price in constant time.

Code Solutions

class StockPrice:
    def __init__(self):
        self.prices = {}  # Dictionary to hold the price at each timestamp
        self.latest_timestamp = 0  # To track the latest timestamp
        self.max_heap = []  # Max heap to track maximum price
        self.min_heap = []  # Min heap to track minimum price

    def update(self, timestamp: int, price: int) -> None:
        # If the timestamp is new, we add it to the dict and heaps
        if timestamp in self.prices:
            # Update the max and min heaps if the price is changing
            old_price = self.prices[timestamp]
            self.max_heap.remove(-old_price)
            self.min_heap.remove(old_price)
        
        self.prices[timestamp] = price
        self.latest_timestamp = max(self.latest_timestamp, timestamp)

        # Add new price to the heaps
        heapq.heappush(self.max_heap, -price)  # Store negative for max heap
        heapq.heappush(self.min_heap, price)

    def current(self) -> int:
        return self.prices[self.latest_timestamp]

    def maximum(self) -> int:
        # Ensure the max heap's top is valid
        while -self.max_heap[0] not in self.prices.values():
            heapq.heappop(self.max_heap)
        return -self.max_heap[0]

    def minimum(self) -> int:
        # Ensure the min heap's top is valid
        while self.min_heap[0] not in self.prices.values():
            heapq.heappop(self.min_heap)
        return self.min_heap[0]