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)
1import heapq
2
3class StockPrice
In this solution, we maintain maxHeap for potential maximum prices and minHeap for potential minimum prices. Each update involves pushing the price to both heaps. Current retrieval from heaps requires cleaning invalid top entries until top reflects a valid timestamp. Thus, maximum and minimum methods traverse heap roots for the latest price associations using a heap invariant.