#2034

Medium

LeetCode Problem Workspace

Stock Price Fluctuation

Design an efficient algorithm for managing stock price fluctuations with incorrect and unordered data in a data stream.

hash table design heap priority queue data stream ordered set

Problem Statement

You are given a stream of stock price records, each consisting of a timestamp and a corresponding price. Due to the volatile nature of the stock market, these records are not in order, and some records may be incorrect. Later records may update previous ones with the correct price at the same timestamp.

Design an algorithm that provides the following methods: update(timestamp, price) - updates the price for a specific timestamp, current() - returns the latest stock price, maximum() - returns the highest price recorded, and minimum() - returns the lowest price recorded. The algorithm should handle the corrections efficiently and support queries that may come after the updates.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Efficient Data Structure Selection

We can use a hash table to store stock prices by their timestamps and a priority queue (heap) to efficiently track the current maximum and minimum prices. The update function will check if the timestamp already exists and update the value accordingly.

Handling Corrections and Ordering

In the case of timestamp corrections, we need to ensure that the data remains consistent. This can be achieved by maintaining an ordered set or heap to reflect the changes in price efficiently without reordering the entire data structure.

Optimizing Queries

For querying the maximum and minimum prices efficiently, the heap structure allows us to access these values in logarithmic time, ensuring quick responses for these operations even with large numbers of records.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the update operation is O(log N) due to the heap insertion, while current(), maximum(), and minimum() queries can be answered in O(1) time. Space complexity is O(N) as we store the records in a hash table and maintain heaps for price tracking.

What Interviewers Usually Probe

Understanding how to efficiently handle unordered data streams.
Familiarity with data structures like hash tables, heaps, and ordered sets.
Ability to design solutions that can handle data corrections without reordering the entire dataset.

Common Pitfalls or Variants

Common pitfalls

Failing to account for efficient price correction handling, which could lead to incorrect maximum or minimum results.
Not considering the potential impact of unordered data, causing slow updates and queries.
Overcomplicating the solution with unnecessary structures, leading to poor performance.

Follow-up variants

What if we have a large number of queries and need to optimize for multiple updates and queries at once?
How would the solution change if the data were to be processed offline (all queries given at once)?
What if the price updates could be negative or zero, requiring extra validation?

FAQ

How can I efficiently handle unordered stock price records?

Use hash tables to store stock prices by timestamps and a priority queue (heap) to maintain maximum and minimum prices.

What is the time complexity for querying the current, maximum, or minimum stock price?

Each of these queries can be answered in O(1) time, while the update operation takes O(log N) time.

How would the solution change if stock prices are updated multiple times for the same timestamp?

The solution should update the price in the hash table and adjust the heap accordingly, ensuring that only the latest price is used for queries.

What if the stock prices have to be handled offline in batches?

For offline processing, you can pre-process the updates and then apply them in order using a similar structure to handle multiple queries efficiently.

Can I solve this problem without using heaps?

While it's possible, using heaps helps achieve efficient O(log N) operations for maximum and minimum queries. Without heaps, queries could become slower.

terminal

Solution

Solution 1: Hash Table + Ordered Set

We define the following data structures or variables:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class StockPrice:
    def __init__(self):
        self.d = {}
        self.ls = SortedList()
        self.last = 0

    def update(self, timestamp: int, price: int) -> None:
        if timestamp in self.d:
            self.ls.remove(self.d[timestamp])
        self.d[timestamp] = price
        self.ls.add(price)
        self.last = max(self.last, timestamp)

    def current(self) -> int:
        return self.d[self.last]

    def maximum(self) -> int:
        return self.ls[-1]

    def minimum(self) -> int:
        return self.ls[0]


# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()

Continue Practicing

#2102 sequentially ordinal rank tracker #1912 design movie rental system #1825 finding mk average