Stock Price Fluctuation

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem

StockPrice: update(timestamp, price), current(), maximum(), minimum(). Prices can be corrected (same timestamp updated).

Key insight: Map timestamp→price + sorted multiset (or two heaps with lazy deletion) for max/min.

Solutions

# Python
from sortedcontainers import SortedList

class StockPrice:
    def __init__(self):
        self.prices = {}
        self.sorted = SortedList()
        self.max_ts = 0

    def update(self, timestamp, price):
        if timestamp in self.prices:
            self.sorted.remove(self.prices[timestamp])
        self.prices[timestamp] = price
        self.sorted.add(price)
        self.max_ts = max(self.max_ts, timestamp)

    def current(self):
        return self.prices[self.max_ts]

    def maximum(self):
        return self.sorted[-1]

    def minimum(self):
        return self.sorted[0]
// C++
class StockPrice {
    map<int,int> ts_price;
    multiset<int> prices;
    int maxTs = 0;
public:
    void update(int ts, int price) {
        if(ts_price.count(ts)) prices.erase(prices.find(ts_price[ts]));
        ts_price[ts]=price; prices.insert(price);
        maxTs=max(maxTs,ts);
    }
    int current(){return ts_price[maxTs];}
    int maximum(){return *prices.rbegin();}
    int minimum(){return *prices.begin();}
};
// Java
class StockPrice {
    Map<Integer,Integer> tsPrice=new HashMap<>();
    TreeMap<Integer,Integer> priceCnt=new TreeMap<>();
    int maxTs=0;
    public void update(int ts, int price) {
        if(tsPrice.containsKey(ts)){int old=tsPrice.get(ts);priceCnt.merge(old,-1,Integer::sum);if(priceCnt.get(old)==0)priceCnt.remove(old);}
        tsPrice.put(ts,price); priceCnt.merge(price,1,Integer::sum); maxTs=Math.max(maxTs,ts);
    }
    public int current(){return tsPrice.get(maxTs);}
    public int maximum(){return priceCnt.lastKey();}
    public int minimum(){return priceCnt.firstKey();}
}
// JavaScript
class StockPrice {
    constructor(){this.prices={};this.sorted=[];this.maxTs=0;}
    update(ts,price){
        if(ts in this.prices){const old=this.prices[ts];const i=this.sorted.indexOf(old);if(i>=0)this.sorted.splice(i,1);}
        this.prices[ts]=price;
        let p=this.sorted.findIndex(x=>x>=price);
        if(p===-1)this.sorted.push(price);else this.sorted.splice(p,0,price);
        if(ts>this.maxTs)this.maxTs=ts;
    }
    current(){return this.prices[this.maxTs];}
    maximum(){return this.sorted[this.sorted.length-1];}
    minimum(){return this.sorted[0];}
}

Complexity

  • update: O(log n), min/max/current: O(1)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro