I was running through a leetcode problem. and found a solution in the discussion section
problem- https://leetcode.com/problems/stock-price-fluctuation/
solution-
class StockPrice { HashMap<Integer, Integer> hm; //timestamp,price TreeMap<Integer, Integer> tm; //price, frequency int current; public StockPrice() { hm = new HashMap<>(); tm = new TreeMap<>(); current = 0; } public void update(int timestamp, int price) { //check whether latest timestamp or current timestamp is larger... current = Math.max(current, timestamp); //if timesatamp already present if(hm.containsKey(timestamp)) { int oldprice=hm.get(timestamp); if(tm.get(oldprice)==1){ tm.remove(oldprice); // } else{ tm.put(oldprice, tm.get(oldprice)-1); } } //update new price in hm hm.put(timestamp, price); //update new frequency of new price in treemap tm.put (price, tm.getOrDefault(price,0)+1); } public int current() { return hm.get(current); } public int maximum() { return tm.lastKey(); } public int minimum() { return tm.firstKey(); } }
-
tm.put(oldprice, tm.get(oldprice)-1);
-
tm.put (price, tm.getOrDefault(price,0)+1);
Advertisement
Answer
To solve the problem you need to know how often the stock is traded for a particular price.
An example:
- it was traded at timestamp 1 for 10, at timestamp 2 for 5. Now the maximum price is 10. (There was one trade for 10, one trade for 5)
- the price for timestamp 1 is updated to 3. Now the maximum price is 5. (There was one trade for 3, one trade for 5)
Another example:
- it was traded at timestamp 1 for 10, at timestamp 2 for 5, at timestamp 3 for 10. The maximum price is also 10. (There were two trades for 10, one trade for 5)
- the price for timestamp 1 is updated to 3. Now the maximum price is still 10 (because of the trade at timestamp 3). (There was one trade for 10, one trade for 3, one trade for 5)
With
tm.put (price, tm.getOrDefault(price,0)+1);
it is noted that one more trade occurred for a specific price.
When an older trade is updated,
if (tm.get(oldprice)==1) { tm.remove(oldprice); // } else { tm.put(oldprice, tm.get(oldprice)-1); }
either removes the entry for the old price (if there was only one trade for that price) or notes that there was one trade less for that price.