Sponsored
Sponsored
This approach utilizes a HashMap to store the price corresponding to each timestamp and a SortedMap to dynamically maintain the counts of each price, enabling efficient tracking of maximum and minimum prices. The HashMap allows quick updates and access to any timestamp's price, while the SortedMap keeps track of occurrences of each price value.
Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1).
Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price.
1from sortedcontainers import SortedDict
2
3class StockPrice:
4 def __init__(self):
5 self.timestamp_to_price = {}
6 self.price_counts = SortedDict()
7 self.latest_time = -1
8
9 def update(self, timestamp: int, price: int):
10 if timestamp in self.timestamp_to_price:
11 old_price = self.timestamp_to_price[timestamp]
12 self.price_counts[old_price] -= 1
13 if self.price_counts[old_price] == 0:
14 del self.price_counts[old_price]
15
16 self.timestamp_to_price[timestamp] = price
17 if price in self.price_counts:
18 self.price_counts[price] += 1
19 else:
20 self.price_counts[price] = 1
21
22 self.latest_time = max(self.latest_time, timestamp)
23
24 def current(self) -> int:
25 return self.timestamp_to_price[self.latest_time]
26
27 def maximum(self) -> int:
28 return self.price_counts.peekitem(-1)[0]
29
30 def minimum(self) -> int:
31 return self.price_counts.peekitem(0)[0]We maintain prices of each timestamp in a dictionary (timestamp_to_price), and use a SortedDict to keep track of the number of occurrences of each price (price_counts). Upon an update, if the timestamp already exists, we decrement the count of its old price. Then we update the timestamp with the new price and maintain the latest timestamp seen so far. Current, maximum, and minimum methods utilize the data structures to fetch results quickly.
This approach uses a max heap (priority queue) for tracking the maximum price and a min heap for the minimum prices. Updates ensure that any obsolete prices are removed, and heap roots can quickly provide max/min prices. Furthermore, checks against the current timestamp allow discarding outdated entries efficiently.
Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments.
Space Complexity: O(n)
1#include <queue>
2#include <unordered_map>
3
4class StockPrice {
5public:
StockPrice() : latestTime(0) {}
void update(int timestamp, int price) {
timePriceMap[timestamp] = price;
latestTime = std::max(latestTime, timestamp);
maxHeap.push({price, timestamp});
minHeap.push({-price, timestamp});
}
int current() {
return timePriceMap[latestTime];
}
int maximum() {
while (!maxHeap.empty() && timePriceMap[maxHeap.top().second] != maxHeap.top().first) {
maxHeap.pop();
}
return maxHeap.top().first;
}
int minimum() {
while (!minHeap.empty() && timePriceMap[minHeap.top().second] != -minHeap.top().first) {
minHeap.pop();
}
return -minHeap.top().first;
}
private:
std::unordered_map<int, int> timePriceMap;
std::priority_queue<std::pair<int, int>> maxHeap;
std::priority_queue<std::pair<int, int>> minHeap;
int latestTime;
};In C++, priority queues help manage and continuously re-evaluate max/min conditions. The process involves inserting into two heaps on each update. Lazy removal is used to discard outdated references until the heap root reflects the valid prices.