LeetCode 2034 - Stock Price Fluctuation

LeetCode Problem 2034

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Heap (Priority Queue), Data Stream, Ordered Set

Solution

Here’s a complete, detailed technical solution guide for LeetCode 2034 - Stock Price Fluctuation following your formatting and content requirements.

Problem Understanding

The problem presents a stream of stock price records where each record consists of a timestamp and a price. However, the stream is not guaranteed to be chronological, and some records may correct previous incorrect prices for the same timestamp.

Our task is to design a StockPrice class that efficiently supports:

Updating the price at a timestamp (which may correct previous data).
Querying the latest price (the price at the largest timestamp).
Querying the maximum price among all current records.
Querying the minimum price among all current records.

The input constraints indicate that timestamps and prices can go up to $10^9$ and there can be up to $10^5$ updates or queries. This precludes naive linear scans on every query because it could lead to $O(n^2)$ behavior in the worst case.

Key observations:

We must track prices per timestamp to handle updates correctly.
Queries for maximum and minimum must reflect corrections efficiently.
current() requires knowing the largest timestamp at any point.

Edge cases to consider:

Updates correcting a previous price.
Maximum or minimum prices being updated due to corrections.
Only one timestamp recorded so far.

Approaches

Brute Force

The naive approach is to store all (timestamp, price) pairs in a list or dictionary.

For update(), simply insert or replace the timestamp.
For current(), iterate through all timestamps to find the largest one.
For maximum() and minimum(), iterate through all stored prices each time.

This works correctly but is inefficient. Each query for maximum or minimum would require $O(n)$ time, and with up to $10^5$ calls, this could lead to a total time complexity of $O(n^2)$.

Optimal Approach

The key insight is to use appropriate data structures to maintain current, max, and min efficiently:

Use a hash map to map timestamps to prices for constant-time updates and corrections.
Track the latest timestamp separately for constant-time current().
Maintain two heaps (priority queues):

A min-heap for minimum price queries.
A max-heap for maximum price queries.

Store (price, timestamp) in the heaps. When a price is corrected, the heap may contain stale entries. Before returning max/min, we pop stale entries until the top is consistent with the current timestamp-to-price mapping.

This approach ensures that update() is $O(\log n)$ for heap insertions, and maximum(), minimum() are $O(\log n)$ amortized due to lazy removal of stale entries. current() is $O(1)$.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per query	O(n)	Simple storage; queries iterate through all records
Optimal	O(log n) per update/query	O(n)	Uses hash map + min/max heaps for efficiency and lazy deletion

Algorithm Walkthrough

Initialize Data Structures:

Create a dictionary timestamp_to_price to store the latest price for each timestamp. Initialize latest_timestamp as 0. Use min_heap and max_heap to maintain prices. 2. Update Operation:

Update timestamp_to_price[timestamp] = price.
Update latest_timestamp = max(latest_timestamp, timestamp).
Push (price, timestamp) to min_heap.
Push (-price, timestamp) to max_heap (negating price for max-heap simulation).

Current Operation:

Return timestamp_to_price[latest_timestamp].

Maximum Operation:

While max_heap[0] is stale (top timestamp's price != stored price), pop it.
Return -max_heap[0][0].

Minimum Operation:

While min_heap[0] is stale (top timestamp's price != stored price), pop it.
Return min_heap[0][0].

Why it works: The heaps allow efficient retrieval of min/max while the hash map ensures correctness despite stale entries. Lazy deletion ensures that corrected entries do not affect the result, and the latest timestamp is always tracked for current().

Python Solution

import heapq

class StockPrice:

    def __init__(self):
        self.timestamp_to_price = {}
        self.latest_timestamp = 0
        self.min_heap = []
        self.max_heap = []

    def update(self, timestamp: int, price: int) -> None:
        self.timestamp_to_price[timestamp] = price
        self.latest_timestamp = max(self.latest_timestamp, timestamp)
        heapq.heappush(self.min_heap, (price, timestamp))
        heapq.heappush(self.max_heap, (-price, timestamp))

    def current(self) -> int:
        return self.timestamp_to_price[self.latest_timestamp]

    def maximum(self) -> int:
        while True:
            price, timestamp = self.max_heap[0]
            if -price == self.timestamp_to_price[timestamp]:
                return -price
            heapq.heappop(self.max_heap)

    def minimum(self) -> int:
        while True:
            price, timestamp = self.min_heap[0]
            if price == self.timestamp_to_price[timestamp]:
                return price
            heapq.heappop(self.min_heap)

Implementation Notes:

min_heap stores (price, timestamp) naturally.
max_heap stores (-price, timestamp) to simulate a max-heap.
Lazy deletion handles corrected prices efficiently.

Go Solution

package main

import (
    "container/heap"
)

type PriceTimestamp struct {
    price, timestamp int
}

type MinHeap []PriceTimestamp
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].price < h[j].price }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any) { *h = append(*h, x.(PriceTimestamp)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type MaxHeap []PriceTimestamp
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].price > h[j].price }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any) { *h = append(*h, x.(PriceTimestamp)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type StockPrice struct {
    timestampToPrice map[int]int
    latestTimestamp  int
    minHeap          *MinHeap
    maxHeap          *MaxHeap
}

func Constructor() StockPrice {
    mh := &MinHeap{}
    hh := &MaxHeap{}
    heap.Init(mh)
    heap.Init(hh)
    return StockPrice{
        timestampToPrice: make(map[int]int),
        minHeap:          mh,
        maxHeap:          hh,
        latestTimestamp:  0,
    }
}

func (this *StockPrice) Update(timestamp int, price int) {
    this.timestampToPrice[timestamp] = price
    if timestamp > this.latestTimestamp {
        this.latestTimestamp = timestamp
    }
    heap.Push(this.minHeap, PriceTimestamp{price, timestamp})
    heap.Push(this.maxHeap, PriceTimestamp{price, timestamp})
}

func (this *StockPrice) Current() int {
    return this.timestampToPrice[this.latestTimestamp]
}

func (this *StockPrice) Maximum() int {
    for {
        top := (*this.maxHeap)[0]
        if this.timestampToPrice[top.timestamp] == top.price {
            return top.price
        }
        heap.Pop(this.maxHeap)
    }
}

func (this *StockPrice) Minimum() int {
    for {
        top := (*this.minHeap)[0]
        if this.timestampToPrice[top.timestamp] == top.price {
            return top.price
        }
        heap.Pop(this.minHeap)
    }
}

Go Notes:

Separate MinHeap and MaxHeap structs are implemented using container/heap.
Lazy deletion is handled similarly to Python.
MaxHeap is implemented by reversing the comparison logic.

Worked Examples

For input:

update(1, 10)
update(2, 5)
current() -> 5
maximum() -> 10
update(1, 3)
maximum() -> 5
update(4, 2)
minimum() -> 2

Trace