Skip to content

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)}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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 rbegin(timestampToPrice)->second;
  }

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

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

 private:
  map<int, int> timestampToPrice;
  map<int, int> pricesCount;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class StockPrice {
  public void update(int timestamp, int price) {
    if (timestampToPrice.containsKey(timestamp)) {
      final int prevPrice = timestampToPrice.get(timestamp);
      pricesCount.merge(prevPrice, -1, Integer::sum);
      if (pricesCount.get(prevPrice) == 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<>();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class StockPrice {
 public:
  void update(int timestamp, int price) {
    if (timestampToPrice.count(timestamp)) {
      const int prevPrice = timestampToPrice[timestamp];
      prices.erase(prices.equal_range(prevPrice).first);
    }
    timestampToPrice[timestamp] = price;
    prices.insert(price);
  }

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

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

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

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