Stock Price Fluctuations

XXX. Stock Price Fluctuations

Heap

HashMap

Problem Statement:

Implement a system to monitor stock prices over time. The system should support the following operations efficiently:

• update(int timestamp, int price): Updates the stock price at a specific timestamp.
• current(): Returns the latest stock price.
• maximum(): Returns the maximum stock price observed so far.
• minimum(): Returns the minimum stock price observed so far.

Algorithm:

1. Use a **HashMap** to store the latest price for each timestamp:
   • Key: Timestamp
   • Value: Price
2. Use two **PriorityQueues** to track the minimum and maximum prices:
   • Min Heap for retrieving the smallest price.
   • Max Heap for retrieving the largest price.
3. During update:
   • Update the timestamp-price map.
   • Add the updated price and timestamp to both heaps.
4. For maximum() and minimum():
   • Check the top element of the heap.
   • If the top element's price does not match the latest price in the HashMap (stale value), remove it and check the next.
   • Repeat until a valid price is found.

Complexity:

Time Complexity:

• update(): O(log n) due to heap insertions.
• current(): O(1) as HashMap lookup is constant time.
• maximum() and minimum(): O(log n) amortized due to heap adjustments.

Space Complexity: O(n), where n is the number of timestamps.

Java Implementation:

class StockPrice {
    private int latestTime; // Tracks the most recent timestamp
    private Map timestampPriceMap; // Maps timestamp to stock price
    private PriorityQueue minHeap, maxHeap; // Min and Max heaps for price tracking

    public StockPrice() {
        latestTime = 0;
        timestampPriceMap = new HashMap<>();
        
        // Min heap to track minimum prices
        minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // Max heap to track maximum prices
        maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    }
    
    // Updates the stock price at a specific timestamp
    public void update(int timestamp, int price) {
        latestTime = Math.max(latestTime, timestamp); // Update the latest time
        timestampPriceMap.put(timestamp, price); // Update the price in the map
        
        // Add the updated price to both heaps
        minHeap.add(new int[]{price, timestamp});
        maxHeap.add(new int[]{price, timestamp});
    }
    
    // Returns the latest stock price
    public int current() {
        return timestampPriceMap.get(latestTime);
    }
    
    // Returns the maximum stock price observed so far
    public int maximum() {
        int[] top = maxHeap.peek(); // Check the top element in max heap
        
        // Remove stale values until a valid price is found
        while (timestampPriceMap.get(top[1]) != top[0]) {
            maxHeap.poll();
            top = maxHeap.peek();
        }
        
        return top[0];
    }
    
    // Returns the minimum stock price observed so far
    public int minimum() {
        int[] top = minHeap.peek(); // Check the top element in min heap
        
        // Remove stale values until a valid price is found
        while (timestampPriceMap.get(top[1]) != top[0]) {
            minHeap.poll();
            top = minHeap.peek();
        }
        
        return top[0];
    }
}
                

Explanation:

• **`update()`**:
  • Updates the latest timestamp and price in the HashMap.
  • Adds the updated price and timestamp to both heaps.
• **`current()`**:
  • Retrieves the price for the most recent timestamp using the HashMap.
• **`maximum()` and `minimum()`**:
  • Repeatedly checks the top element of the heap and removes stale values that do not match the latest price in the HashMap.
  • Stops once a valid price is found.