2034. Stock Price Fluctuation

Approach 1: Ordered Map

• Time: Constructor: $O(1)$, update(timestamp: int, price: int), current(), maximum(), minimum(): $O(\log n)$
• Space: $O(|\texttt{update(timestamp: int, price: int)}|)$

C++JavaPython

class StockPrice {
 public:
  void update(int timestamp, int price) {
    if (timestampToPrice.count(timestamp)) {
      const int prevPrice = timestampToPrice[timestamp];
      if (--pricesCount[prevPrice] == 0)
        pricesCount.erase(prevPrice);
    }
    timestampToPrice[timestamp] = price;
    ++pricesCount[price];
  }

  int current() {
    return timestampToPrice.rbegin()->second;
  }

  int maximum() {
    return pricesCount.rbegin()->first;
  }

  int minimum() {
    return pricesCount.begin()->first;
  }

 private:
  map<int, int> timestampToPrice;
  map<int, int> pricesCount;
};

class StockPrice {
  public void update(int timestamp, int price) {
    if (timestampToPrice.containsKey(timestamp)) {
      final int prevPrice = timestampToPrice.get(timestamp);
      if (pricesCount.merge(prevPrice, -1, Integer::sum) == 0)
        pricesCount.remove(prevPrice);
    }
    timestampToPrice.put(timestamp, price);
    pricesCount.merge(price, 1, Integer::sum);
  }

  public int current() {
    return timestampToPrice.lastEntry().getValue();
  }

  public int maximum() {
    return pricesCount.lastKey();
  }

  public int minimum() {
    return pricesCount.firstKey();
  }

  private TreeMap<Integer, Integer> timestampToPrice = new TreeMap<>();
  private TreeMap<Integer, Integer> pricesCount = new TreeMap<>();
}

from sortedcontainers import SortedDict


class StockPrice:
  def __init__(self):
    self.timestampToPrice = SortedDict()
    self.pricesCount = SortedDict()

  def update(self, timestamp: int, price: int) -> None:
    if timestamp in self.timestampToPrice:
      prevPrice = self.timestampToPrice[timestamp]
      self.pricesCount[prevPrice] -= 1
      if self.pricesCount[prevPrice] == 0:
        del self.pricesCount[prevPrice]
    self.timestampToPrice[timestamp] = price
    self.pricesCount[price] = self.pricesCount.get(price, 0) + 1

  def current(self) -> int:
    return self.timestampToPrice.peekitem(-1)[1]

  def maximum(self) -> int:
    return self.pricesCount.peekitem(-1)[0]

  def minimum(self) -> int:
    return self.pricesCount.peekitem(0)[0]

Approach 2: C++ std::multiset

• Time: Constructor: $O(1)$, update(timestamp: int, price: int), current(), maximum(), minimum(): $O(\log n)$
• Space: $O(|\texttt{update(timestamp: int, price: int)}|)$

C++

class StockPrice {
 public:
  void update(int timestamp, int price) {
    if (const auto it = timestampToPrice.find(timestamp);
        it != timestampToPrice.cend()) {
      const int prevPrice = it->second;
      prices.erase(prices.equal_range(prevPrice).first);
    }
    timestampToPrice[timestamp] = price;
    prices.insert(price);
  }

  int current() {
    return timestampToPrice.rbegin()->second;
  }

  int maximum() {
    return *prices.rbegin();
  }

  int minimum() {
    return *prices.begin();
  }

 private:
  map<int, int> timestampToPrice;
  multiset<int> prices;
};