Stock Price Fluctuation

MediumOrdered Map · Hash Map · Design🧩 Ordered Set (TreeMap)LeetCode #2034 ↗Updated Oct 30, 2026

Problem

A price feed sends (timestamp, price) records out of order, and a later record for an existing timestamp corrects (overwrites) the earlier one. Design StockPrice with update(timestamp, price), current() (price at the latest timestamp seen), and maximum() / minimum() over the current, corrected prices of all timestamps.

Inputupdate(1,10) update(2,5) current()Output5

Inputmaximum() update(1,3) maximum()Output10, then 5

1 ≤ timestamp, price ≤ 10⁹ · ≤ 10⁵ calls · queries only after at least one update

Try it yourself

Java

class StockPrice {
    public void update(int timestamp, int price) {
        
    }

    public int current() {
        
    }

    public int maximum() {
        
    }

    public int minimum() {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Corrections can remove the current max/min, so a single running max is not enough. Keep a multiset of live prices (price → count in a TreeMap): decrement the old price, increment the new one, and read both ends.

PatternOrdered Set (TreeMap)

Instinct Keys keep arriving or leaving and you must ask "what is the nearest key below/above x?" or "current min/max" each time - reach for TreeMap/TreeSet.

Memory hack A HashMap with a sense of direction - floor looks down, ceiling looks up, and both answer in log time while the data keeps changing.

Open the Ordered Set (TreeMap) guide →

Approaches

Brute ForceList of (timestamp, price) Pairs

Time O(n) every opSpace O(n)

Store records in a list; update scans to overwrite, current scans for the latest timestamp, max/min scan all prices.

Java

class StockPrice {
    private final List<int[]> records = new ArrayList<>();
    private int latest = 0;

    public void update(int timestamp, int price) {
        latest = Math.max(latest, timestamp);
        for (int[] r : records) {
            if (r[0] == timestamp) { r[1] = price; return; }
        }
        records.add(new int[]{timestamp, price});
    }

    public int current() {
        for (int[] r : records) if (r[0] == latest) return r[1];
        return -1;
    }

    public int maximum() { return records.stream().mapToInt(r -> r[1]).max().getAsInt(); }

    public int minimum() { return records.stream().mapToInt(r -> r[1]).min().getAsInt(); }
}

Obviously correct, but every operation is linear.

BetterHashMap + Latest Timestamp

Time O(1) update/current, O(n) max/minSpace O(n)

A HashMap<timestamp, price> makes corrections a plain put, and remembering the largest timestamp makes current a single lookup. Max/min still scan all values.

Java

class StockPrice {
    private final Map<Integer, Integer> priceAt = new HashMap<>();
    private int latest = 0;

    public void update(int timestamp, int price) {
        priceAt.put(timestamp, price);
        latest = Math.max(latest, timestamp);
    }

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

    public int maximum() { return Collections.max(priceAt.values()); }

    public int minimum() { return Collections.min(priceAt.values()); }
}

Fast writes, but queries stay O(n) — bad for query-heavy workloads.

OptimalHashMap + TreeMap Price Multiset

Time O(log n) update/max/min, O(1) currentSpace O(n)

Add a TreeMap<price, count> of the live prices. On a correction, decrement the old price (drop it at 0), then count the new one; max/min are lastKey()/firstKey(). Counts matter because several timestamps can share a price.

Java

class StockPrice {
    private final Map<Integer, Integer> priceAt = new HashMap<>();
    private final TreeMap<Integer, Integer> freq = new TreeMap<>(); // price -> count
    private int latest = 0;

    public void update(int timestamp, int price) {
        Integer old = priceAt.put(timestamp, price);
        if (old != null && freq.merge(old, -1, Integer::sum) == 0) freq.remove(old);
        freq.merge(price, 1, Integer::sum);
        latest = Math.max(latest, timestamp);
    }

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

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

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

Every operation is logarithmic or better — scales to 10⁵ calls.

Pro tip

Alternative: max-heap + min-heap of [price, timestamp] with lazy deletion — pop tops whose price no longer matches priceAt.

At a glance

Level	Approach	Time	Space
Brute Force	List of (timestamp, price) Pairs	`O(n) every op`	`O(n)`
Better	HashMap + Latest Timestamp	`O(1) update/current, O(n) max/min`	`O(n)`
Optimal	HashMap + TreeMap Price Multiset	`O(log n) update/max/min, O(1) current`	`O(n)`

Common pitfalls

Keeping one running max/min — a correction can invalidate it.
A TreeSet of prices — loses duplicates; removing one copy removes all.
Treating the last call as current — current means the largest timestamp.

Interview tips

Ask whether updates arrive in order and whether corrections are possible.
Point out why a count per price is required (shared prices).
Compare TreeMap (exact, O(log n)) vs heaps with lazy deletion (amortised).

Pattern

Multiset with updates → maintain min/max under insert, overwrite and delete.

My notes saved in this browser