How do you solve Stock Price Fluctuation on LeetCode?

Stock Price Fluctuation (LeetCode #2034) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(n) space complexity. Key insight: Using a hash map allows for O(1) access to the latest price.

What is the time complexity of Stock Price Fluctuation ?

The optimal solution for Stock Price Fluctuation runs in O(log n) time and uses O(n) space. The time complexity is O(log n) for updates and O(1) for current, maximum, and minimum operations due to the use of heaps and hash maps.

What is the brute force solution for Stock Price Fluctuation ?

The brute force approach for Stock Price Fluctuation is Brute Force, with O(n²) time complexity and O(n) space complexity. In the brute force approach, we can use a simple list to store all the prices and timestamps. For each query, we will iterate through the list to find the latest, maximum, or minimum price. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(log n).

What are the interview tips for Stock Price Fluctuation ?

Think about how to efficiently manage updates and queries. Consider edge cases, such as updating the same timestamp multiple times. Practice explaining your thought process clearly during the interview.

What are common mistakes when solving Stock Price Fluctuation ?

Not updating the heaps correctly when prices change. Forgetting to handle duplicate timestamps appropriately.

#2034

Stock Price Fluctuation

Medium

Hash TableDesignHeap (Priority Queue)Data StreamOrdered SetHash MapHeap

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(n)	O(n)

💡

Intuition

Time O(log n)Space O(n)

In the optimal approach, we can use a combination of a hash map to store the latest prices by timestamp and two heaps (or a sorted data structure) to keep track of the maximum and minimum prices efficiently. This allows us to perform all operations in O(log n) time.

⚙️

Algorithm

6 steps

1Step 1: Use a hash map to store the latest price for each timestamp.
2Step 2: Maintain a max-heap for the maximum price and a min-heap for the minimum price.
3Step 3: For the update operation, update the hash map and adjust the heaps accordingly.
4Step 4: For the current operation, return the value from the hash map for the latest timestamp.
5Step 5: For the maximum operation, return the top of the max-heap.
6Step 6: For the minimum operation, return the top of the min-heap.

solution.py37 lines

1import heapq
2
3class StockPrice:
4    def __init__(self):
5        self.timestamp_price = {}
6        self.max_heap = []
7        self.min_heap = []
8        self.latest_timestamp = 0
9    
10    def update(self, timestamp, price):
11        if timestamp in self.timestamp_price:
12            old_price = self.timestamp_price[timestamp]
13            self.max_heap.remove((-old_price, timestamp))
14            self.min_heap.remove((old_price, timestamp))
15            heapq.heapify(self.max_heap)
16            heapq.heapify(self.min_heap)
17        self.timestamp_price[timestamp] = price
18        heapq.heappush(self.max_heap, (-price, timestamp))
19        heapq.heappush(self.min_heap, (price, timestamp))
20        self.latest_timestamp = max(self.latest_timestamp, timestamp)
21    
22    def current(self):
23        return self.timestamp_price[self.latest_timestamp]
24    
25    def maximum(self):
26        while self.max_heap:
27            price, timestamp = self.max_heap[0]
28            if timestamp in self.timestamp_price and self.timestamp_price[timestamp] == -price:
29                return -price
30            heapq.heappop(self.max_heap)
31    
32    def minimum(self):
33        while self.min_heap:
34            price, timestamp = self.min_heap[0]
35            if timestamp in self.timestamp_price and self.timestamp_price[timestamp] == price:
36                return price
37            heapq.heappop(self.min_heap)

ℹ

Complexity note: The time complexity is O(log n) for updates and O(1) for current, maximum, and minimum operations due to the use of heaps and hash maps.

1Using a hash map allows for O(1) access to the latest price.
2Heaps provide efficient retrieval of maximum and minimum prices.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.