LC 2034


Solution to LeetCode 2034 Stock Price Fluctuation

LeetCode 2034

Stock Price Fluctuation (Medium). [link]

Use a HashMap to store and update the time stamp. Use SortedList to store the price in ascending order.

from sortedcontainers import SortedList

class StockPrice(object):

    def __init__(self):
        self.price = SortedList()
        self.Hash = {}
        self.currentTime = 0

    def update(self, timestamp, price):
        """
        :type timestamp: int
        :type price: int
        :rtype: None
        """
        if timestamp in self.Hash:
            self.price.discard(self.Hash[timestamp])
        self.price.add(price)
        self.Hash[timestamp] = price
        self.currentTime = max(self.currentTime, timestamp)

    def current(self):
        """
        :rtype: int
        """
        return self.Hash[self.currentTime]

    def maximum(self):
        """
        :rtype: int
        """
        return self.price[-1]
        
    def minimum(self):
        """
        :rtype: int
        """
        return self.price[0]

We can also use Min Heap and Max Heap to keep track of the maximum and minimum of the price.

class StockPrice(object):

    def __init__(self):
        self.maxPrice = []
        self.minPrice = []
        self.Hash = {}
        self.currentTime = 0

    def update(self, timestamp, price):
        """
        :type timestamp: int
        :type price: int
        :rtype: None
        """
        heappush(self.maxPrice, (-price, timestamp))
        heappush(self.minPrice, (price, timestamp))
        self.Hash[timestamp] = price
        self.currentTime = max(self.currentTime, timestamp)

    def current(self):
        """
        :rtype: int
        """
        return self.Hash[self.currentTime]

    def maximum(self):
        """
        :rtype: int
        """
        while True:
            price, timestamp = self.maxPrice[0]
            if -price == self.Hash[timestamp]:
                return -price
            heappop(self.maxPrice)
        
    def minimum(self):
        """
        :rtype: int
        """
        while True:
            price, timestamp = self.minPrice[0]
            if price == self.Hash[timestamp]:
                return price
            heappop(self.minPrice)

  TOC