Skip to main content
Talentd

Stock Price Fluctuation - Solution & Explanation

MediumHash TableDesignHeap (Priority Queue)Data Stream15 min readAsked at: Amazon, Meta, Atlassian +3
Practice this problem

Problem Statement

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 the price of the stock at the given timestamp.
  • 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 105 calls will be made in total to update, current, maximum, and minimum.
  • current, maximum, and minimum will be called only after update has 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.

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.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonC++

Python

C++

Complexity

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)

Try this approach in the editor →

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 timestamp timestamp to price. If timestamp already exists, we need to first remove its corresponding price from the ordered set, and then update it to price. Otherwise, we directly update it to price. Then, we need to update last to max(last, timestamp). The time complexity is O(log n).
  • current(): return the price corresponding to last. The time complexity is O(1).
  • maximum(): return the maximum value in the ordered set. The time complexity is O(log n).
  • minimum(): return the minimum value in the ordered set. The time complexity is O(log n).

The space complexity is O(n), where n is the number of update operations.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap + SortedMap (TreeMap / Ordered Map)O(log n) per update and queryO(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 DeletionO(log n) amortizedO(n)Preferred when heaps are easier to implement or when solving typical data stream problems.

Video Solution

STOCK PRICE FLUCTUATION | LEETCODE # 2034 | PYTHON HEAP SOLUTION • Cracking FAANG • 4,708 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Stock Price Fluctuation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Time Based Key-Value Store