Stock Price Fluctuation

Medium Heaps Advanced Original on LeetCode

Reported atAtlassian

Stock Price Fluctuation is a medium heaps problem solved with the advanced pattern. The best approach, optimal (hash map + two heaps with lazy deletion), runs in O(log n) amortized per call time and O(u) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from hash map + linear scan up.

Problem

A stream of stock price records arrives, each a pair (timestamp, price). The stream is messy: records can arrive in any order, and a later record with a timestamp you have already seen corrects the earlier price for that timestamp (the old price is no longer valid).

Design the class StockPrice:

  • StockPrice() creates an empty tracker.
  • update(int timestamp, int price) records price at timestamp, replacing any earlier price for that timestamp.
  • current() returns the price at the largest timestamp recorded so far.
  • maximum() returns the highest price among all currently valid records.
  • minimum() returns the lowest price among all currently valid records.

Examples

Example 1

Input
StockPrice(), update(2, 40), update(5, 25), current(), maximum(), update(2, 12), maximum(), minimum()
Output
25, 40, 25, 12
Why
After two records the latest time is 5 (price 25) and the highest is 40. Then the record at time 2 is corrected to 12, so 40 no longer exists: the highest is now 25 and the lowest is 12.

Example 2

Input
StockPrice(), update(7, 90), update(3, 60), update(9, 75), current(), minimum(), update(9, 50), current(), minimum()
Output
75, 60, 50, 50
Why
Records arrive out of order; the current price belongs to time 9, the largest timestamp, even though time 3 arrived later than time 7. Correcting time 9 to 50 changes both the current price and the minimum.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Hash map + linear scanupdate/current O(1), maximum/minimum O(n)O(n)
Optimal (hash map + two heaps with lazy deletion)O(log n) amortized per callO(u)

1Hash map + linear scan

Timeupdate/current O(1), maximum/minimum O(n)n is the number of distinct timestamps; each extreme query visits all of them.
SpaceO(n)One map entry per distinct timestamp.

Store the latest price for every timestamp in a hash map and track the largest timestamp. current is a lookup; maximum and minimum scan every stored price.

  1. update: priceAt[timestamp] = price; latest = max(latest, timestamp).
  2. current: return priceAt[latest].
  3. maximum / minimum: loop over all values in the map.
class StockPrice {
    private final Map<Integer, Integer> priceAt = new HashMap<>();
    private int latest = 0;

    public StockPrice() {}

    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() {
        int best = Integer.MIN_VALUE;
        for (int p : priceAt.values()) best = Math.max(best, p);
        return best;
    }

    public int minimum() {
        int best = Integer.MAX_VALUE;
        for (int p : priceAt.values()) best = Math.min(best, p);
        return best;
    }
}

2Optimal (hash map + two heaps with lazy deletion)

TimeO(log n) amortized per callEvery update pushes two entries (O(log u)); each stale entry is popped at most once, so the cleanup cost is paid for by the update that created it.
SpaceO(u)u is the number of updates; each leaves one entry in each heap until it is popped.

Keep the map and latest as before, and also push every (price, timestamp) record onto a max-heap and a min-heap. A heap top is valid only if the map still holds that price for that timestamp; otherwise the record was overwritten, so pop it and look again. Each record is popped at most once per heap.

  1. update: write the map, update latest, push (price, timestamp) onto both heaps.
  2. current: return priceAt[latest].
  3. maximum: while the max-heap top's price differs from priceAt[top.timestamp], pop it; return the top's price.
  4. minimum: the same with the min-heap.
class StockPrice {
    private final Map<Integer, Integer> priceAt = new HashMap<>();
    private final PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
    private final PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    private int latest = 0;

    public StockPrice() {}

    public void update(int timestamp, int price) {
        priceAt.put(timestamp, price);
        latest = Math.max(latest, timestamp);
        maxHeap.offer(new int[] { price, timestamp });
        minHeap.offer(new int[] { price, timestamp });
    }

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

    public int maximum() {
        return validTop(maxHeap);
    }

    public int minimum() {
        return validTop(minHeap);
    }

    private int validTop(PriorityQueue<int[]> heap) {
        while (priceAt.get(heap.peek()[1]) != heap.peek()[0]) heap.poll();
        return heap.peek()[0];
    }
}

Edge cases to test

  • The same timestamp corrected several times (only the last price counts)
  • Correcting the record that currently holds the maximum or minimum
  • Updates that arrive with older timestamps than ones already seen
  • Many records with the same price

Hints

Hint 1

Keep a map from timestamp to its latest price, and remember the largest timestamp seen so far for current.

Hint 2

Scanning the whole map for every maximum or minimum is O(n). Can a heap give you the extreme price faster?

Hint 3

When a timestamp is corrected, its old heap entry becomes stale. Instead of removing it, store (price, timestamp) pairs and discard a heap top whose price no longer matches the map (lazy deletion).

FAQ

What is the best time complexity for Stock Price Fluctuation?

Optimal (hash map + two heaps with lazy deletion) runs in O(log n) amortized per call time and O(u) extra space. Every update pushes two entries (O(log u)); each stale entry is popped at most once, so the cleanup cost is paid for by the update that created it.

Which pattern does Stock Price Fluctuation use?

It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Trapping Rain Water II.

Is there a brute force solution for Stock Price Fluctuation?

Yes. Hash map + linear scan takes update/current O(1), maximum/minimum O(n) time and O(n) space. Store the latest price for every timestamp in a hash map and track the largest timestamp.

Which edge cases should I test for Stock Price Fluctuation?

The same timestamp corrected several times (only the last price counts); Correcting the record that currently holds the maximum or minimum; Updates that arrive with older timestamps than ones already seen; Many records with the same price.