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.
1class StockPrice {
2 constructor() {
3 this.timestampToPrice = new Map();
4 this.priceCounts = new Map();
5 this.latestTimestamp = 0;
6 }
7
8 update(timestamp, price) {
9 if (this.timestampToPrice.has(timestamp)) {
10 const oldPrice = this.timestampToPrice.get(timestamp);
11 this.priceCounts.set(oldPrice, this.priceCounts.get(oldPrice) - 1);
12 if (this.priceCounts.get(oldPrice) === 0) {
13 this.priceCounts.delete(oldPrice);
14 }
15 }
16
17 this.timestampToPrice.set(timestamp, price);
18 this.priceCounts.set(price, (this.priceCounts.get(price) || 0) + 1);
19 this.latestTimestamp = Math.max(this.latestTimestamp, timestamp);
20 }
21
22 current() {
23 return this.timestampToPrice.get(this.latestTimestamp);
24 }
25
26 maximum() {
27 return Math.max(...this.priceCounts.keys());
28 }
29
30 minimum() {
31 return Math.min(...this.priceCounts.keys());
32 }
33}In JavaScript, we use Map objects for efficient data storage and retrieval. The update function maintains correct price counts and updates the latest timestamp. The current, maximum, and minimum methods access required values efficiently using the Map’s methods and built-in functions.
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.