Problem statement

A feed reports a stock's price at various timestamps, but the records arrive out of order, and some are corrections: a later record for a timestamp that was already reported replaces the earlier price for that timestamp.

Write the class StockPrice:

• StockPrice() starts with no records.
• void update(int timestamp, int price) records that the price at timestamp is price (correcting any earlier record for that timestamp).
• int current() returns the price at the latest timestamp recorded.
• int maximum() and int minimum() return the highest and lowest price over all timestamps, using the current (corrected) price of each.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["StockPrice","update","update","current","maximum","update","maximum","update","minimum"]
[[],[1,10],[2,5],[],[],[1,3],[],[4,2],[]]
Output: [null,null,null,5,10,null,5,null,2]
Explanation: After prices 10 at time 1 and 5 at time 2, the latest timestamp is 2 (price 5) and the maximum is 10. Correcting time 1 to 3 makes the maximum 5. With 2 at time 4, the minimum is 2.

Example 2

Input: ["StockPrice","update","update","current","update","current","minimum"]
[[],[7,40],[3,90],[],[7,100],[],[]]
Output: [null,null,null,40,null,100,90]
Explanation: Time 3 arrives after time 7 but is older, so current stays 40. Correcting time 7 to 100 changes current to 100; the minimum is then 90.

Constraints

• 1 <= timestamp, price <= 10^9
• At most 10^5 calls are made to update, current, maximum and minimum in total
• current, maximum and minimum are called only after at least one update

Hints for Stock Price Fluctuation

1. Hint 1

   Keep a map from timestamp to its current price, and track the largest timestamp seen — that answers current.

2. Hint 2

   For maximum/minimum you need the extremes of a multiset of prices that supports replacing one value: an ordered map from price to how many timestamps hold it does that in O(log n).

3. Hint 3

   Alternatively push every (price, timestamp) into a max-heap and a min-heap and discard stale entries lazily: when the top's price no longer equals the map's price for its timestamp, pop it and look again.

How to solve Stock Price Fluctuation

A hash map holds each timestamp's current price; an ordered multiset (or two heaps with lazy deletion) holds the prices so the extremes come out in O(log n) even after corrections.

Approach

1. update(t, p): if t already has a price old, remove one copy of old from the multiset. Store price[t] = p, add p to the multiset, and set latest = max(latest, t).
2. current(): return price[latest].
3. maximum() / minimum(): return the multiset's largest / smallest key.
4. Heap variant: push (p, t) into both heaps on every update; before answering, pop the top while price[top.t] != top.p (it was corrected).

Why it works

The multiset always contains exactly one entry per timestamp — its current price — because a correction removes the old value before adding the new. Its extremes are therefore the answers. In the heap variant every stale entry is recognised by comparing with the map, and an entry that matches is a live price, so the first matching top is the true extreme; each entry is popped at most once.

Complexity

• Time — O(log n) per update, maximum and minimum (amortised for the heaps); O(1) for current
• Space — O(n)

Pitfalls

• current is the price at the largest timestamp, not the most recent call — records arrive out of order.
• A correction must remove the old price; otherwise maximum and minimum can return a price that no longer exists.
• With a multiset, erase one copy of the old price, not all of them — two timestamps may share a price.

Reference solution

Python

import heapq

class StockPrice:

    def __init__(self):
        self.price = {}
        self.latest = 0
        self.max_heap = []  # (-price, timestamp), stale entries dropped lazily
        self.min_heap = []  # (price, timestamp)

    def update(self, timestamp: int, price: int) -> None:
        self.price[timestamp] = price
        self.latest = max(self.latest, timestamp)
        heapq.heappush(self.max_heap, (-price, timestamp))
        heapq.heappush(self.min_heap, (price, timestamp))

    def current(self) -> int:
        return self.price[self.latest]

    def maximum(self) -> int:
        h = self.max_heap
        while self.price[h[0][1]] != -h[0][0]:  # corrected since it was pushed
            heapq.heappop(h)
        return -h[0][0]

    def minimum(self) -> int:
        h = self.min_heap
        while self.price[h[0][1]] != h[0][0]:
            heapq.heappop(h)
        return h[0][0]

Java

class StockPrice {
    private HashMap<Integer, Integer> price = new HashMap<>();
    private TreeMap<Integer, Integer> counts = new TreeMap<>(); // price -> how many timestamps hold it
    private int latest = 0;

    public StockPrice() {
    }

    public void update(int timestamp, int price) {
        Integer old = this.price.put(timestamp, price);
        if (old != null) { // a correction: drop one copy of the old price
            if (counts.get(old) == 1) counts.remove(old); else counts.put(old, counts.get(old) - 1);
        }
        counts.merge(price, 1, Integer::sum);
        latest = Math.max(latest, timestamp);
    }

    public int current() {
        return price.get(latest);
    }

    public int maximum() {
        return counts.lastKey();
    }

    public int minimum() {
        return counts.firstKey();
    }
}

C++

class StockPrice {
    unordered_map<int, int> price;
    multiset<int> prices; // one entry per timestamp
    int latest = 0;
public:
    StockPrice() {}

    void update(int timestamp, int price) {
        auto it = this->price.find(timestamp);
        if (it != this->price.end()) prices.erase(prices.find(it->second)); // a correction: drop one copy
        this->price[timestamp] = price;
        prices.insert(price);
        latest = max(latest, timestamp);
    }

    int current() {
        return price[latest];
    }

    int maximum() {
        return *prices.rbegin();
    }

    int minimum() {
        return *prices.begin();
    }
};

JavaScript

// A min-heap of [key, timestamp] pairs; the max-heap stores key = -price.
function spPush(h, item) {
    var i = h.length;
    h.push(item);
    while (i > 0 && h[(i - 1) >> 1][0] > item[0]) { h[i] = h[(i - 1) >> 1]; i = (i - 1) >> 1; }
    h[i] = item;
}

function spPop(h) {
    var last = h.pop();
    if (h.length === 0) return;
    var i = 0;
    for (;;) {
        var l = 2 * i + 1, r = l + 1, m = i, mv = last[0];
        if (l < h.length && h[l][0] < mv) { m = l; mv = h[l][0]; }
        if (r < h.length && h[r][0] < mv) m = r;
        if (m === i) break;
        h[i] = h[m];
        i = m;
    }
    h[i] = last;
}

var StockPrice = function() {
    this.price = new Map();
    this.latest = 0;
    this.maxH = [];
    this.minH = [];
};

StockPrice.prototype.update = function(timestamp, price) {
    this.price.set(timestamp, price);
    if (timestamp > this.latest) this.latest = timestamp;
    spPush(this.maxH, [-price, timestamp]);
    spPush(this.minH, [price, timestamp]);
};

StockPrice.prototype.current = function() {
    return this.price.get(this.latest);
};

StockPrice.prototype.maximum = function() {
    var h = this.maxH;
    while (this.price.get(h[0][1]) !== -h[0][0]) spPop(h); // corrected since it was pushed
    return -h[0][0];
};

StockPrice.prototype.minimum = function() {
    var h = this.minH;
    while (this.price.get(h[0][1]) !== h[0][0]) spPop(h);
    return h[0][0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium