{x}
blog image

Stock Price Fluctuation

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.

Solution Explanation: Stock Price Fluctuation

This problem requires designing a data structure to efficiently handle stock price updates and queries for the latest, maximum, and minimum prices. The optimal approach uses a combination of a hash table and an ordered set (or a similar structure offering efficient retrieval of min/max elements).

Approach: Hash Table + Ordered Set

  1. Data Structures:

    • d (HashMap/Dictionary): Stores the timestamp as the key and the price as the value. This allows for O(1) lookup of the price for a given timestamp.
    • ls (SortedSet/TreeSet/Multiset): Stores all the unique prices encountered. This enables O(log n) retrieval of minimum and maximum prices (where n is the number of unique prices). A Multiset (or the equivalent handling of duplicates) is needed because the same price may appear multiple times at different timestamps.

  2. update(timestamp, price):

    • Handle Existing Timestamp: If the timestamp already exists in d, remove the old price from ls (handling duplicates appropriately).
    • Update Price: Update the price for the timestamp in d.
    • Add New Price: Add the new price to ls.
    • Update Latest Timestamp: Track the last timestamp to efficiently get the latest price.

  3. current():

    • Simply return the price associated with the last timestamp from d. O(1) operation.

  4. maximum() and minimum():

    • Directly retrieve the maximum and minimum elements from ls. O(1) operation for retrieving the extremal elements from a sorted structure.

Time and Space Complexity Analysis:

  • Time Complexity:
    • update(): O(log n), dominated by the insertion and removal operations in the ordered set.
    • current(): O(1).
    • maximum() and minimum(): O(1).
    • Overall: The time complexity is largely determined by the update operations, making the overall time complexity O(m log n), where m is the number of update calls and n is the number of unique prices. In the worst case, n can be m.
  • Space Complexity: O(m), where m is the number of update calls, due to storing the timestamps and prices in d and the unique prices in ls.

Code Examples (Python, Java, C++, Go)

The code examples in the previous response demonstrate this approach using appropriate data structures for each language. The Python code uses SortedList (from sortedcontainers), which offers efficient sorted list functionality. Java uses TreeMap for its ordered set capabilities. C++ uses multiset. Go utilizes a redblacktree implementation (you'll need to include a suitable redblack tree library). The choice of data structures is crucial for achieving the optimal time complexity. Note that in Go the merge helper function helps to handle the update logic and duplicate counts efficiently.

This detailed explanation should clarify the algorithmic approach, data structures, complexity analysis, and code implementation for efficiently solving the Stock Price Fluctuation problem.