Stock Price Fluctuation — Dual Heap with Timestamp Correction Handling

Problem Statement#

Design a class StockPrice that tracks stock prices with the following operations:

• update(timestamp, price) — update the stock price at timestamp. If the timestamp already exists, it corrects the price.
• current() — return the latest stock price (price at the highest timestamp).
• maximum() — return the maximum stock price across all recorded timestamps.
• minimum() — return the minimum stock price across all recorded timestamps.

Constraints:

• 1 <= timestamp, price <= 10^9
• At most 10^5 calls total.
• current, maximum, minimum are called only when the stock price has been updated at least once.

Examples:

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:
update(1,10): timestamp=1 → price=10
update(2,5):  timestamp=2 → price=5
current() → 5 (latest timestamp=2)
maximum() → 10
update(1,3):  CORRECTION! timestamp=1 price changes from 10 to 3
maximum() → 5 (10 is gone, max is now 5)
update(4,2):  timestamp=4 → price=2
minimum() → 2

Why This Problem Matters#

Stock Price Fluctuation is a medium design problem that tests a subtle but important real-world scenario: out-of-order and correctable updates. Amazon and Meta use it because their financial and monitoring systems must handle exactly this: stock feeds that deliver updates non-sequentially, and corrections that arrive after initial reports.

The problem is deceptively tricky because of the correction case. If you use only a max-heap and min-heap for maximum and minimum queries, a correction invalidates old heap entries. You need a way to reconcile the correction with the existing heap state.

The elegant solution uses a timestamp-to-price map (for O(1) correction lookup) and a sorted multiset (for O(log n) max/min queries with correct handling of removals). This combination — a hash map plus a sorted structure — is a recurring design pattern in interview problems that require both point queries and range/order queries.

Python's SortedList from sortedcontainers, Java's TreeMap, and C++'s multiset all serve this role. If you're in a language without a built-in sorted structure, you can fall back to heaps with lazy deletion (the same pattern from Sliding Window Median).

The Core Insight#

Three pieces of state:

1. ts_price: a hash map from timestamp to current price. Enables O(1) lookup of the old price when a correction arrives.
2. sorted_prices: a sorted multiset (or SortedList) of all current prices. Enables O(log n) minimum and maximum queries by looking at the first and last elements.
3. max_ts: the highest timestamp seen so far. Enables O(1) current() queries.

On update(timestamp, price):

• If timestamp already exists in ts_price: remove the old price from sorted_prices, then add the new price.
• Otherwise: just add the new price to sorted_prices.
• Update ts_price[timestamp] = price.
• Update max_ts = max(max_ts, timestamp).

On current(): Return ts_price[max_ts]. On maximum(): Return sorted_prices[-1] (last element). On minimum(): Return sorted_prices[0] (first element).

The key insight is that SortedList (or its equivalent) supports O(log n) insertion, removal, and first/last element access — giving O(log n) for all operations.

Visual Dry Run#

Operations: update(1,10), update(2,5), current(), maximum(), update(1,3), maximum()
 
update(1,10):
  ts_price = {1:10}. sorted = [10]. max_ts=1.
 
update(2,5):
  ts_price = {1:10, 2:5}. sorted = [5,10]. max_ts=2.
 
current() → ts_price[2] = 5. ✓
 
maximum() → sorted[-1] = 10. ✓
 
update(1,3): CORRECTION for timestamp 1.
  Old price = ts_price[1] = 10. Remove 10 from sorted: sorted = [5].
  Add 3: sorted = [3,5]. ts_price = {1:3, 2:5}. max_ts=2.
 
maximum() → sorted[-1] = 5. ✓

Solution (Optimal)#

from sortedcontainers import SortedList
 
class StockPrice:
    def __init__(self):
        self.ts_price = {}        # timestamp → price
        self.sorted_prices = SortedList()  # sorted multiset of prices
        self.max_ts = 0
    
    def update(self, timestamp: int, price: int) -> None:
        # Handle correction: remove old price if timestamp already recorded
        if timestamp in self.ts_price:
            old_price = self.ts_price[timestamp]
            self.sorted_prices.remove(old_price)
        
        # Update records
        self.ts_price[timestamp] = price
        self.sorted_prices.add(price)
        self.max_ts = max(self.max_ts, timestamp)
    
    def current(self) -> int:
        return self.ts_price[self.max_ts]
    
    def maximum(self) -> int:
        return self.sorted_prices[-1]
    
    def minimum(self) -> int:
        return self.sorted_prices[0]

class StockPrice {
    constructor() {
        this.tsPrice = new Map();   // timestamp → price
        this.sortedPrices = [];     // sorted array (simulates SortedList)
        this.maxTs = 0;
    }
    
    update(timestamp, price) {
        // Handle correction
        if (this.tsPrice.has(timestamp)) {
            const oldPrice = this.tsPrice.get(timestamp);
            const idx = this._binarySearch(oldPrice);
            this.sortedPrices.splice(idx, 1);  // O(n) splice — see note
        }
        
        this.tsPrice.set(timestamp, price);
        this._insertSorted(price);
        if (timestamp > this.maxTs) this.maxTs = timestamp;
    }
    
    _binarySearch(val) {
        let lo = 0, hi = this.sortedPrices.length - 1;
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (this.sortedPrices[mid] === val) return mid;
            else if (this.sortedPrices[mid] < val) lo = mid + 1;
            else hi = mid - 1;
        }
        return lo;
    }
    
    _insertSorted(val) {
        let lo = 0, hi = this.sortedPrices.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (this.sortedPrices[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        this.sortedPrices.splice(lo, 0, val);
    }
    
    current() {
        return this.tsPrice.get(this.maxTs);
    }
    
    maximum() {
        return this.sortedPrices[this.sortedPrices.length - 1];
    }
    
    minimum() {
        return this.sortedPrices[0];
    }
}

Note on JavaScript: Array.splice is O(n) due to shifting. For true O(log n), use a balanced BST (not natively available in JS). In interviews, the sorted array approach is acceptable and the binary search for find/insert is O(log n); only the shift is O(n).

Complexity Analysis:

• update: O(log n) with SortedList/TreeMap; O(n) with array
• current, maximum, minimum: O(1) with SortedList; O(1) with sorted array
• Space: O(n) — one entry per unique timestamp

Common Mistakes#

• Using a simple max-heap and min-heap without handling corrections. When a price is corrected, the old price becomes invalid in both heaps. Without lazy deletion or a sorted set, max/min queries return stale values.
• Forgetting to handle the case where current() is called before any update. The constraints guarantee at least one update before current is called, but still good to check.
• Tracking max_ts incorrectly when corrections arrive. A correction never changes max_ts unless the corrected timestamp was max_ts. But since max_ts = max(max_ts, timestamp), this is handled automatically.
• Removing the wrong instance from a multiset. If price 10 appears twice and you remove 10, you should remove only one copy. Python's SortedList.remove removes one instance; C++'s multiset.erase(it) removes one instance.
• Using ts_price as a sorted structure. ts_price is a hash map for O(1) lookup; sorting by timestamp is only needed for max_ts (which you track separately).

Follow-up Questions#

1. What if prices can be 0 or negative? Does the algorithm change? (No — SortedList handles any comparable values.)
2. Add a getAtTimestamp(ts) operation in O(1). Is this already supported? (Yes — ts_price[ts].)
3. Implement this with two heaps and lazy deletion instead of SortedList. How does the update logic change for corrections?
4. What if timestamps arrive strictly in order (no corrections)? Can you use a simpler data structure? (Yes — just track max and min with O(1) update.)
5. What is the worst-case space usage if there are 10^5 updates with the same timestamp? (O(1) space in sorted_prices since it stores one price per unique timestamp.)
6. How would you serialize and deserialize the StockPrice state for persistence?

Key Takeaways#

• The correction case is the crux: when a timestamp is updated, you must remove the old price from the sorted structure before adding the new one — a hash map gives O(1) old price lookup.
• Use a SortedList (Python sortedcontainers) or TreeMap (Java) to support O(log n) insertion, deletion, and first/last element access simultaneously.
• Track max_ts separately with a simple max() update — current() then runs in O(1).
• The hash-map-plus-sorted-structure combination recurs in any problem requiring both point queries and order statistics with corrections.
• Two-heap-plus-lazy-deletion is an alternative: mark corrected prices as deleted in a counter, prune lazily when they surface at heap tops.
• Amazon and Meta use this problem because real stock feeds deliver out-of-order corrections — candidates must design for mutability, not just append-only streams.
• All operations achieve O(log n) with SortedList; current(), maximum(), and minimum() are O(1) since they access the first/last elements of the sorted list.