2034. Stock Price Fluctuation
Asked at Atlassian
Difficulty
Medium
Time
O(log n) per update, O(1) for cu
Space
O(n)
Pattern
Hash Table
Companies
1
Problem
Design a class StockPrice that keeps track of a stock's price over time. Records arrive one at a time, and they may arrive out of order. A record can also be wrong: a later record with the same timestamp replaces the earlier price for that timestamp.
Implement these methods:
update(timestamp, price)— record the price at that timestamp. If a record for that timestamp already exists, overwrite it.current()— return the price at the largest timestamp seen so far.maximum()— return the largest price among all current records.minimum()— return the smallest price among all current records.
Only the newest price for each timestamp counts. If a timestamp is overwritten, its old price must no longer affect maximum() or minimum().
Out-of-order records with corrections
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
Examples
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []][null, null, null, 5, 10, null, 5, null, 2]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Naive approach: store all (timestamp, price) pairs in a list. current() is O(1) (last element). maximum() and minimum() scan the entire list each time: O(n). This is too slow if maximum()/minimum() are called frequently.
Better: use a hash map (dictionary) mapping timestamp to price for O(1) updates and lookups. For max/min, maintain two heaps: a max-heap for maximum and a min-heap for minimum. This gives O(1) current, O(log n) update, O(1) amortized max/min.
The problem: heaps do not support efficient deletion of arbitrary elements. When you update a price at an existing timestamp, the old price is still in the heap. Solution: lazy deletion. Mark the old entry as stale in the hash map. When popping from the heap, skip entries where the hash map value does not match the heap top.
Data structures:
price_map:dict[timestamp] -> pricefor O(1) lookups.max_heap: stores(-price, timestamp)for max price (negate for max-heap in Python).min_heap: stores(price, timestamp)for min price.latest_timestamp: tracks the most recent timestamp forcurrent().
Lazy deletion example: timestamp 3 initially has price 100. Heap has (100, 3). Update timestamp 3 to price 50. Now price_map[3] = 50, but heap still has (100, 3). When you pop (100, 3) from min-heap, check price_map[3] == 100? No (it's 50). Discard and pop again.
Complexity: update() is O(log n) (two heap pushes). current() is O(1). maximum() and minimum() are O(log n) amortized (popping stale entries). Total space: O(n).
Optimal Approach
Maintain a hash map (price_map) mapping timestamp to price, a max-heap (max_heap) storing (-price, timestamp), and a min-heap (min_heap) storing (price, timestamp). Also track latest_timestamp.
update(timestamp, price):
- Store
price_map[timestamp] = price. - Push
(-price, timestamp)ontomax_heap. - Push
(price, timestamp)ontomin_heap. - Update
latest_timestampiftimestampis newer.
current():
- Return
price_map[latest_timestamp].
maximum():
- Peek at
max_heap[0]. Whileprice_map[heap_top.timestamp] != -heap_top.price, pop (stale entry). Return-max_heap[0][0].
minimum():
- Same lazy deletion logic on
min_heap. Returnmin_heap[0][0].
Walkthrough: update(1, 10), update(2, 5), update(1, 20).
price_map = {1: 20, 2: 5}. Heaps have stale (10, 1).maximum(): heap top is (-10, 1).price_map[1]is 20, not 10. Pop. Next is (-20, 1).price_map[1]is 20 = -(-20). Return 20.minimum(): heap top is (5, 2).price_map[2]is 5. Return 5.
Time: O(log n) update, O(1) current, O(log n) amortized max/min. Space: O(n).
Hash map plus two lazy heaps
What Trips People Up in Real Interviews
Forgetting that updating the same timestamp overwrites the old price. The heap still contains the old (price, timestamp) pair. Without lazy deletion, you would return stale max/min values.
Using a TreeMap / SortedDict for max/min. While this works (O(log n) for max/min), heaps are more commonly expected in interviews and the lazy deletion pattern is a valuable signal.
Not tracking the latest timestamp for current(). If you only use heaps, you cannot efficiently get the latest price. You need either a hash map or a separate variable.
Pushing duplicate entries into the heap without lazy deletion. Do NOT try to remove old entries from the heap — it is O(n). Instead, push new entries and skip stale ones when popping.
Forgetting that Python's heapq is a min-heap. For a max-heap, negate the price: push (-price, timestamp) and negate again when reading back.
Solution Code
O(log n) per update, O(1) for cu timeimport heapq
class StockPrice:
def __init__(self):
self.price_map = {}
self.max_heap = []
self.min_heap = []
self.latest_timestamp = 0
def update(self, timestamp: int, price: int) -> None:
self.price_map[timestamp] = price
heapq.heappush(self.max_heap, (-price, timestamp))
heapq.heappush(self.min_heap, (price, timestamp))
self.latest_timestamp = max(self.latest_timestamp, timestamp)
def current(self) -> int:
return self.price_map[self.latest_timestamp]
def maximum(self) -> int:
while self.max_heap:
price, ts = self.max_heap[0]
if self.price_map.get(ts) == -price:
return -price
heapq.heappop(self.max_heap)
return -1
def minimum(self) -> int:
while self.min_heap:
price, ts = self.min_heap[0]
if self.price_map.get(ts) == price:
return price
heapq.heappop(self.min_heap)
return -1Frequently Asked Questions
What is the Stock Price Fluctuation problem?
Design a data structure that tracks stock prices over time, supporting three operations: `update(timestamp, price)` to record a new price, `current()` to return the latest price, and `maximum()` / `minimum()` to return the highest and lowest prices recorded. Prices can be updated at the same timestamp, overwriting the previous value.
How do you solve Stock Price Fluctuation?
The optimal approach runs in O(log n) per update, O(1) for cu time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Stock Price Fluctuation?
Stock Price Fluctuation is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Stock Price Fluctuation?
- Forgetting that updating the same timestamp overwrites the old price. The heap still contains the old (price, timestamp) pair. Without lazy deletion, you would return stale max/min values.
- Using a `TreeMap` / `SortedDict` for max/min. While this works (`O(log n)` for max/min), heaps are more commonly expected in interviews and the lazy deletion pattern is a valuable signal.
- Not tracking the latest timestamp for `current()`. If you only use heaps, you cannot efficiently get the latest price. You need either a `hash map` or a separate variable.
- Pushing duplicate entries into the heap without lazy deletion. Do NOT try to remove old entries from the heap — it is `O(n)`. Instead, push new entries and skip stale ones when popping.
- Forgetting that Python's `heapq` is a min-heap. For a max-heap, negate the price: push `(-price, timestamp)` and negate again when reading back.