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.
1import java.util.*;
2
3class StockPrice {
4 private Map<Integer, Integer> timePriceMap;
5 private TreeMap<Integer, Integer> priceCounts;
6 private int latestTime;
7
8 public StockPrice() {
9 timePriceMap = new HashMap<>();
10 priceCounts = new TreeMap<>();
11 latestTime = 0;
12 }
13
14 public void update(int timestamp, int price) {
15 if (timePriceMap.containsKey(timestamp)) {
16 int oldPrice = timePriceMap.get(timestamp);
17 priceCounts.put(oldPrice, priceCounts.get(oldPrice) - 1);
18 if (priceCounts.get(oldPrice) == 0) {
19 priceCounts.remove(oldPrice);
20 }
21 }
22 timePriceMap.put(timestamp, price);
23 priceCounts.put(price, priceCounts.getOrDefault(price, 0) + 1);
24 latestTime = Math.max(latestTime, timestamp);
25 }
26
27 public int current() {
28 return timePriceMap.get(latestTime);
29 }
30
31 public int maximum() {
32 return priceCounts.lastKey();
33 }
34
35 public int minimum() {
36 return priceCounts.firstKey();
37 }
38}The Java implementation uses a combination of a HashMap to store timestamp-price pairs and a TreeMap for managing price frequencies. The update operation adjusts these data structures to reflect current state, keeping track of the latest timestamp encountered. TreeMap structures offer convenient access methods for minimum and maximum keys.
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.