Stock Price Fluctuation

medium hash map design heap data stream ordered set

Problem

Design a StockPrice class that supports update(t, p), current(), maximum() and minimum() over a stream of (timestamp, price) records. If an update arrives for an existing timestamp, the older price is overwritten.

Inputupdates = [(1,10), (2,5), (1,3)]

Outputcurrent=5, max=5, min=3

Timestamp 1's price was rewritten from 10 to 3; (1,10) becomes stale in the heaps.

updates (t:p separated by ';')

import heapq

class StockPrice:
    def __init__(self):
        self.latest = 0
        self.prices = {}
        self.max_heap = []  # (-price, t)
        self.min_heap = []  # (price, t)

    def update(self, t, p):
        self.prices[t] = p
        self.latest = max(self.latest, t)
        heapq.heappush(self.max_heap, (-p, t))
        heapq.heappush(self.min_heap, (p, t))

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

    def maximum(self):
        while -self.max_heap[0][0] != self.prices[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)
        return -self.max_heap[0][0]

    def minimum(self):
        while self.min_heap[0][0] != self.prices[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)
        return self.min_heap[0][0]

class StockPrice {
  constructor() {
    this.latest = 0;
    this.prices = new Map();
    this.maxHeap = []; // entries: [-price, t]
    this.minHeap = []; // entries: [price, t]
  }
  update(t, p) {
    this.prices.set(t, p);
    if (t > this.latest) this.latest = t;
    this._push(this.maxHeap, [-p, t]);
    this._push(this.minHeap, [p, t]);
  }
  current() { return this.prices.get(this.latest); }
  maximum() {
    while (-this.maxHeap[0][0] !== this.prices.get(this.maxHeap[0][1])) this._pop(this.maxHeap);
    return -this.maxHeap[0][0];
  }
  minimum() {
    while (this.minHeap[0][0] !== this.prices.get(this.minHeap[0][1])) this._pop(this.minHeap);
    return this.minHeap[0][0];
  }
  // _push / _pop maintain a binary min-heap by first element.
}

class StockPrice {
    int latest = 0;
    Map<Integer, Integer> prices = new HashMap<>();
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

    public void update(int t, int p) {
        prices.put(t, p);
        latest = Math.max(latest, t);
        maxHeap.offer(new int[]{p, t});
        minHeap.offer(new int[]{p, t});
    }
    public int current()  { return prices.get(latest); }
    public int maximum() {
        while (maxHeap.peek()[0] != prices.get(maxHeap.peek()[1])) maxHeap.poll();
        return maxHeap.peek()[0];
    }
    public int minimum() {
        while (minHeap.peek()[0] != prices.get(minHeap.peek()[1])) minHeap.poll();
        return minHeap.peek()[0];
    }
}

class StockPrice {
    int latest = 0;
    unordered_map<int, int> prices;
    priority_queue<pair<int, int>> maxHeap;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
public:
    void update(int t, int p) {
        prices[t] = p;
        latest = max(latest, t);
        maxHeap.push({p, t});
        minHeap.push({p, t});
    }
    int current() { return prices[latest]; }
    int maximum() {
        while (maxHeap.top().first != prices[maxHeap.top().second]) maxHeap.pop();
        return maxHeap.top().first;
    }
    int minimum() {
        while (minHeap.top().first != prices[minHeap.top().second]) minHeap.pop();
        return minHeap.top().first;
    }
};

Explanation

The tricky part is that an old price can be overwritten, so the heaps can hold stale values. The fix is a lazy approach: store the true price in a map and only clean up wrong heap entries when we actually peek at them.

We keep a prices map from timestamp to its latest price, plus a max-heap and a min-heap that each store (price, timestamp) pairs. Every update(t, p) writes the map, updates latest (the newest timestamp), and pushes the pair into both heaps.

current() is easy: just return prices[latest]. For maximum() and minimum(), we peek at the heap top and compare its stored price against the map. If they differ, that entry is stale (the timestamp was later updated), so we pop it and look again until the top agrees with the map.

Example: updates (1,10), (2,5), (1,3). The map ends as {1: 3, 2: 5}, and latest = 2, so current() is 5. The max-heap top is (10, t=1), but the map says timestamp 1 is now 3, so that entry is dropped and the real max becomes 5; the real min is 3.

Because each pair is pushed once and popped at most once, the cleanup stays cheap on average, giving roughly O(log n) per operation.

Time: O(log n) amortized per op Space: O(n)