Stock Price Fluctuation - Leetcode Solution

The Stock Price Fluctuation problem on Leetcode is a design question that asks us to implement a class that supports two operations:

1. update(price): Update the price of the stock to price.
2. current(): Return the current price of the stock.

We are also asked to implement another method maximum(): Return the maximum price of the stock seen so far.

Approach:

To solve this problem, we can use a priority queue to keep track of the maximum price. Every time a new price is updated, we check if the new price exceeds the maximum, and if it does, we update the maximum price. Then, we add the new price to the priority queue.

The current() function simply returns the last price added to the priority queue, whereas the maximum() function returns the maximum element of the priority queue.

Implementation:

Let's see the code implementation of the above approach:

from queue import PriorityQueue

class StockPrice:

    def __init__(self):
        self.price = {}
        self.maxPrice = float('-inf')
        self.q = PriorityQueue()

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.price:
            self.q.put((self.price[timestamp], timestamp))
            self.price[timestamp] = price
            self.maxPrice = max(self.maxPrice, price)
        else:
            self.price[timestamp] = price
            self.maxPrice = max(self.maxPrice, price)
            self.q.put((price, timestamp))

    def current(self) -> int:
        return self.price[max(self.price.keys())]

    def maximum(self) -> int:
        while not self.q.empty():
            maxPrice, timestamp = self.q.get()
            if timestamp in self.price and self.price[timestamp] == maxPrice:
                return maxPrice
        return self.maxPrice

In the above code implementation, we have created a dictionary to store the price at various timestamps, an instance variable to keep track of the maximum price seen so far, and a priority queue to store the prices in decreasing order.

The update() function updates the price of the stock for a given timestamp. If the timestamp is already present in the dictionary, we update the price for that timestamp and add the old price to the priority queue. If the timestamp is not present in the dictionary, we add the current price to the priority queue. We also update the maximum price seen so far.

The current() function simply returns the last price added to the dictionary.

The maximum() function returns the maximum price seen so far. It applies a while loop till the queue is not empty, then it gets the maximum element from the queue and checks whether the maximum price is present in the dictionary or not. If it is present, it returns the maximum price, else it continues with the while loop till it finds the maximum price. If the maximum price is not yet found, it returns the maximum price seen so far.

Time and Space Complexity:

The time complexity of the update function is O(log N), where N is the number of timestamps. The maximum and current functions are O(1).

The space complexity of the program is O(N), where N is the number of timestamps.

1