Stock Price Fluctuation solution and explanation
Google
9 more videos on this problem
STOCK PRICE FLUCTUATION | LEETCODE # 2034 | PYTHON HEAP SOLUTIONCracking FAANG · 18:44 · 4K views
Stock Price Fluctuation - Google Coding Interview QuestionAlgosWithMichael · 15:11 · 2K views
2034. Stock Price Fluctuation (Leetcode Medium)Programming Live with Larry · 9:12 · 2K views
2034. Stock Price Fluctuation | Leetcode Weekly Contest 262 | C++Gaurav Agrawal · 10:53 · 1K views
Leetcode Weekly Contest 262 | 2034. Stock Price Fluctuation(Medium) in EnglishCompetitive Somya · 5:32 · 918 views
Leetcode 2034. Stock Price Fluctuation (Weekly Contest 262 Q2)Yinghua Hu · 11:37 · 674 views
Leetcode 2034DailyLeetcode · 8:04 · 135 views
Stock Price Fluctuation - Leetcode 2034 - Heap - PythonEffective Coder · 15:32 · 119 views
Amazon Microsoft Google Interview Question 2034. Stock Price FluctuationCodeCoderCoding · 2:13 · 77 views
Mastering Stock Price Fluctuation Problem | LeetCode 2034 Solution ExplainedAlgoMastery · 2:06 · 71 views
The problem
You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.
Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.
Design an algorithm that:
- Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp.
- Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
- Finds the maximum price the stock has been based on the current records.
- Finds the minimum price the stock has been based on the current records.
Implement the StockPrice class:
StockPrice()Initializes the object with no price records.void update(int timestamp, int price)Updates thepriceof the stock at the giventimestamp.int current()Returns the latest price of the stock.int maximum()Returns the maximum price of the stock.int minimum()Returns the minimum price of the stock.
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
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5); // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current(); // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum(); // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3); // The previous timestamp 1 had the wrong price, so it is updated to 3.
// Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum(); // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2); // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum(); // return 2, the minimum price is 2 at timestamp 4.
Constraints:
1 <= timestamp, price <= 109- At most
105calls will be made in total toupdate,current,maximum, andminimum. current,maximum, andminimumwill be called only afterupdatehas been called at least once.
Approach overview
Problem Overview: Design a data structure that processes a stream of stock price updates. Each update provides a timestamp and price. You must support correcting past prices, retrieving the latest price, and efficiently returning the maximum and minimum prices seen so far.
The challenge comes from corrections. A timestamp can appear multiple times, meaning the previous price for that timestamp becomes invalid. Your structure must update efficiently while still answering maximum() and minimum() queries quickly.
Approach 1: HashMap + SortedMap (Ordered Set) (O(log n) per update/query)
Store the latest price for each timestamp in a HashMap. This lets you detect corrections instantly. Maintain another structure that keeps prices sorted, typically a balanced tree such as TreeMap or a sorted multiset. When an update arrives, check if the timestamp already exists. If it does, decrement the frequency of the old price in the sorted structure before inserting the new one. Track the latest timestamp separately to answer current(). The smallest and largest keys in the sorted map give minimum() and maximum(). Updates and deletions both cost O(log n), while space usage is O(n). This approach relies on ordered structures commonly discussed in hash table and ordered set problems.
Approach 2: Priority Queues for Maximum and Minimum (Lazy Removal) (O(log n) per operation)
Instead of maintaining a fully sorted structure, keep two heaps: a max-heap for the maximum price and a min-heap for the minimum price. A HashMap still stores the latest price for each timestamp. Each update pushes the new (price, timestamp) pair into both heaps. Old values remain inside the heaps, which means they may become stale after corrections. Handle this with lazy deletion: whenever you query maximum() or minimum(), repeatedly pop from the heap until the top entry matches the current price stored in the hash map. Heap insertions and removals cost O(log n), and each outdated entry is removed once, giving efficient amortized performance. This design pattern appears often in heap (priority queue) and data stream problems.
Recommended for interviews: The priority queue approach is the most common interview solution because it demonstrates handling stale data with lazy deletion while maintaining fast queries. The HashMap + SortedMap solution is also strong and sometimes simpler in languages with built-in ordered maps like Java's TreeMap or C++ map. Showing awareness of corrections and maintaining consistent state is the key skill interviewers evaluate.
Approach 1: Using HashMap and SortedMap
This approach utilizes a HashMap to store the price corresponding to each timestamp and a SortedMap to dynamically maintain the counts of each price, enabling efficient tracking of maximum and minimum prices. The HashMap allows quick updates and access to any timestamp's price, while the SortedMap keeps track of occurrences of each price value.
from sortedcontainers import SortedDict
class StockPrice:
def __init__(self):
self.timestamp_to_price = {}
self.price_counts = SortedDict()
self.latest_time = -1
def update(self, timestamp: int, price: int):
if timestamp in self.timestamp_to_price:
old_price = self.timestamp_to_price[timestamp]
self.price_counts[old_price] -= 1
if self.price_counts[old_price] == 0:
del self.price_counts[old_price]
self.timestamp_to_price[timestamp] = price
if price in self.price_counts:
self.price_counts[price] += 1
else:
self.price_counts[price] = 1
self.latest_time = max(self.latest_time, timestamp)
def current(self) -> int:
return self.timestamp_to_price[self.latest_time]
def maximum(self) -> int:
return self.price_counts.peekitem(-1)[0]
def minimum(self) -> int:
return self.price_counts.peekitem(0)[0]import java.util.*;
class StockPrice {
private Map<Integer, Integer> timePriceMap;
private TreeMap<Integer, Integer> priceCounts;
private int latestTime;
public StockPrice() {
timePriceMap = new HashMap<>();
priceCounts = new TreeMap<>();
latestTime = 0;
}
public void update(int timestamp, int price) {
if (timePriceMap.containsKey(timestamp)) {
int oldPrice = timePriceMap.get(timestamp);
priceCounts.put(oldPrice, priceCounts.get(oldPrice) - 1);
if (priceCounts.get(oldPrice) == 0) {
priceCounts.remove(oldPrice);
}
}
timePriceMap.put(timestamp, price);
priceCounts.put(price, priceCounts.getOrDefault(price, 0) + 1);
latestTime = Math.max(latestTime, timestamp);
}
public int current() {
return timePriceMap.get(latestTime);
}
public int maximum() {
return priceCounts.lastKey();
}
public int minimum() {
return priceCounts.firstKey();
}
}#include <unordered_map>
#include <map>
class StockPrice {
public:
StockPrice() : latest_time(0) {}
void update(int timestamp, int price) {
if (priceMap.find(timestamp) != priceMap.end()) {
int oldPrice = priceMap[timestamp];
priceCounts[oldPrice]--;
if (priceCounts[oldPrice] == 0) {
priceCounts.erase(oldPrice);
}
}
priceMap[timestamp] = price;
priceCounts[price]++;
latest_time = std::max(latest_time, timestamp);
}
int current() {
return priceMap[latest_time];
}
int maximum() {
return priceCounts.rbegin()->first;
}
int minimum() {
return priceCounts.begin()->first;
}
private:
std::unordered_map<int, int> priceMap;
std::map<int, int> priceCounts;
int latest_time;
};class StockPrice {
constructor() {
this.timestampToPrice = new Map();
this.priceCounts = new Map();
this.latestTimestamp = 0;
}
update(timestamp, price) {
if (this.timestampToPrice.has(timestamp)) {
const oldPrice = this.timestampToPrice.get(timestamp);
this.priceCounts.set(oldPrice, this.priceCounts.get(oldPrice) - 1);
if (this.priceCounts.get(oldPrice) === 0) {
this.priceCounts.delete(oldPrice);
}
}
this.timestampToPrice.set(timestamp, price);
this.priceCounts.set(price, (this.priceCounts.get(price) || 0) + 1);
this.latestTimestamp = Math.max(this.latestTimestamp, timestamp);
}
current() {
return this.timestampToPrice.get(this.latestTimestamp);
}
maximum() {
return Math.max(...this.priceCounts.keys());
}
minimum() {
return Math.min(...this.priceCounts.keys());
}
}We maintain prices of each timestamp in a dictionary (timestamp_to_price), and use a SortedDict to keep track of the number of occurrences of each price (price_counts). Upon an update, if the timestamp already exists, we decrement the count of its old price. Then we update the timestamp with the new price and maintain the latest timestamp seen so far. Current, maximum, and minimum methods utilize the data structures to fetch results quickly.
Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1).
Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price.
Approach 2: Using Priority Queues for Maximum and Minimum
This approach uses a max heap (priority queue) for tracking the maximum price and a min heap for the minimum prices. Updates ensure that any obsolete prices are removed, and heap roots can quickly provide max/min prices. Furthermore, checks against the current timestamp allow discarding outdated entries efficiently.
import heapq
class StockPrice:
def __init__(self):
self.timePriceMap = {}
self.maxHeap = []
self.minHeap = []
self.latestTime = 0
def update(self, timestamp: int, price: int):
self.timePriceMap[timestamp] = price
self.latestTime = max(self.latestTime, timestamp)
heapq.heappush(self.maxHeap, (-price, timestamp))
heapq.heappush(self.minHeap, (price, timestamp))
def current(self) -> int:
return self.timePriceMap[self.latestTime]
def maximum(self) -> int:
while self.maxHeap and self.timePriceMap[self.maxHeap[0][1]] != -self.maxHeap[0][0]:
heapq.heappop(self.maxHeap)
return -self.maxHeap[0][0]
def minimum(self) -> int:
while self.minHeap and self.timePriceMap[self.minHeap[0][1]] != self.minHeap[0][0]:
heapq.heappop(self.minHeap)
return self.minHeap[0][0]#include <queue>
#include <unordered_map>
class StockPrice {
public:
StockPrice() : latestTime(0) {}
void update(int timestamp, int price) {
timePriceMap[timestamp] = price;
latestTime = std::max(latestTime, timestamp);
maxHeap.push({price, timestamp});
minHeap.push({-price, timestamp});
}
int current() {
return timePriceMap[latestTime];
}
int maximum() {
while (!maxHeap.empty() && timePriceMap[maxHeap.top().second] != maxHeap.top().first) {
maxHeap.pop();
}
return maxHeap.top().first;
}
int minimum() {
while (!minHeap.empty() && timePriceMap[minHeap.top().second] != -minHeap.top().first) {
minHeap.pop();
}
return -minHeap.top().first;
}
private:
std::unordered_map<int, int> timePriceMap;
std::priority_queue<std::pair<int, int>> maxHeap;
std::priority_queue<std::pair<int, int>> minHeap;
int latestTime;
};In this solution, we maintain maxHeap for potential maximum prices and minHeap for potential minimum prices. Each update involves pushing the price to both heaps. Current retrieval from heaps requires cleaning invalid top entries until top reflects a valid timestamp. Thus, maximum and minimum methods traverse heap roots for the latest price associations using a heap invariant.
Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments.
Space Complexity: O(n)
Approach 3: Hash Table + Ordered Set
We define the following data structures or variables:
d: a hash table that stores the timestamp and the corresponding price;ls: an ordered set that stores all prices;last: the timestamp of the last update.
Then, we can perform the following operations:
update(timestamp, price): update the price corresponding to the timestamptimestamptoprice. Iftimestampalready exists, we need to first remove its corresponding price from the ordered set, and then update it toprice. Otherwise, we directly update it toprice. Then, we need to updatelasttomax(last, timestamp). The time complexity is O(log n).current(): return the price corresponding tolast. The time complexity isO(1).maximum(): return the maximum value in the ordered set. The time complexity isO(log n).minimum(): return the minimum value in the ordered set. The time complexity isO(log n).
The space complexity is O(n), where n is the number of update operations.
type StockPrice struct {
d map[int]int
ls *redblacktree.Tree
last int
}
func Constructor() StockPrice {
return StockPrice{
d: make(map[int]int),
ls: redblacktree.NewWithIntComparator(),
last: 0,
}
}
func (this *StockPrice) Update(timestamp int, price int) {
merge := func(rbt *redblacktree.Tree, key, value int) {
if v, ok := rbt.Get(key); ok {
nxt := v.(int) + value
if nxt == 0 {
rbt.Remove(key)
} else {
rbt.Put(key, nxt)
}
} else {
rbt.Put(key, value)
}
}
if v, ok := this.d[timestamp]; ok {
merge(this.ls, v, -1)
}
this.d[timestamp] = price
merge(this.ls, price, 1)
this.last = max(this.last, timestamp)
}
func (this *StockPrice) Current() int {
return this.d[this.last]
}
func (this *StockPrice) Maximum() int {
return this.ls.Right().Key.(int)
}
func (this *StockPrice) Minimum() int {
return this.ls.Left().Key.(int)
}
/**
* Your StockPrice object will be instantiated and called as such:
* obj := Constructor();
* obj.Update(timestamp,price);
* param_2 := obj.Current();
* param_3 := obj.Maximum();
* param_4 := obj.Minimum();
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Using HashMap and SortedMap | Time Complexity: Update operation is O(log n), as updating the SortedDict requires logarithmic time. Current, maximum, and minimum operations are O(1). Space Complexity: O(n), where n is the number of timestamps since we store each timestamp and its price. |
| Using Priority Queues for Maximum and Minimum | Time Complexity: Update is O(log n) due to heap operations. Maximum and minimum operations may require O(log n) adjustments. Space Complexity: O(n) |
| Hash Table + Ordered Set | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + SortedMap (TreeMap / Ordered Map) | O(log n) per update and query | O(n) | Best when the language provides a built-in ordered map or multiset and you want clean min/max retrieval. |
| Two Priority Queues with Lazy Deletion | O(log n) amortized | O(n) | Preferred when heaps are easier to implement or when solving typical data stream problems. |
Frequently asked questions
Is Stock Price Fluctuation easy or hard?
Stock Price Fluctuation is classified as a Medium problem. The difficulty comes from handling corrected timestamps while still returning accurate minimum and maximum prices efficiently.
Stock Price Fluctuation Python/Java solution
Python solutions usually use a dictionary plus two heaps with lazy deletion. Java implementations often use a HashMap with a TreeMap or two PriorityQueue structures. Both approaches achieve O(log n) time per update while keeping O(n) memory.
How to solve Stock Price Fluctuation in O(log n)?
Maintain a hash map from timestamp to price and track the latest timestamp. Use either an ordered map (TreeMap or multiset) or two heaps to maintain sorted price information. Each update inserts the new price and removes or invalidates the old one. Maximum and minimum queries then return the top element in O(log n) time or better.
Is Stock Price Fluctuation asked at Google/Amazon/Meta?
Stock Price Fluctuation represents a common interview pattern involving data streams, heaps, and correction handling. Similar designs frequently appear in interviews at companies like Amazon, Google, and Meta where candidates must maintain dynamic statistics with efficient updates.
What is the best approach for Stock Price Fluctuation ?
The most common approach uses two priority queues (a max-heap and a min-heap) combined with a hash map. The hash map stores the latest price for each timestamp, while the heaps track potential maximum and minimum values. Lazy deletion removes outdated entries when they reach the top of the heap. Each operation runs in O(log n) time with O(n) space.
What data structure is used in Stock Price Fluctuation ?
Typical solutions combine a hash table with either a balanced ordered map or priority queues. The hash map tracks the latest price for each timestamp, while the ordered structure or heaps allow fast retrieval of the minimum and maximum prices.
What is the time complexity of Stock Price Fluctuation ?
Efficient implementations run in O(log n) time per update and query. Heap insertion or balanced-tree updates take O(log n), while retrieving the latest price is O(1). The total space complexity is O(n) because all timestamps and prices must be stored.