AlgoMaster Logo

Stock Price Fluctuation

Last Updated: April 3, 2026

medium
4 min read

Understanding the Problem

We're building a stock price tracker that handles an unruly stream of data. Records arrive out of order, and sometimes a correction comes in that overwrites a previous price at the same timestamp. At any point, we need to answer three questions: what's the most recent price, what's the highest price across all timestamps, and what's the lowest?

The "current" price is straightforward if we track which timestamp is the latest. The tricky part is maintaining the maximum and minimum efficiently, especially when corrections happen. If timestamp 1's price changes from 10 to 3, and 10 was the maximum, we can't just decrement a counter. We need to know what the new maximum is after removing 10 from the picture.

The key observation is that corrections make this fundamentally different from a simple "running max/min" problem. We need a data structure that supports both adding new prices and removing old ones (when they get corrected), while still efficiently answering max and min queries.

Key Constraints:

  • 1 <= timestamp, price <= 10^9 -> Values can be large, so we can't use arrays indexed by timestamp or price. We need hash maps and dynamic structures.
  • At most 10^5 total calls -> We need each operation to be better than O(n) to be comfortable. O(log n) per call is the sweet spot, giving us roughly 10^5 * 17 = 1.7 million operations, well within time limits.

Approach 1: Brute Force (Linear Scan)

Intuition

The most natural approach: use a hash map to store the latest price for each timestamp, and track which timestamp is the most recent. For current, just look up the latest timestamp's price. For maximum and minimum, scan through all stored prices every time.

This is simple and correct, but the scan is the problem. Every max/min query walks through every timestamp we've ever seen.

Algorithm

  1. Maintain a hash map mapping timestamps to prices.
  2. Track the latest timestamp seen so far.
  3. On update(timestamp, price), set map[timestamp] = price and update the latest timestamp if this one is newer.
  4. On current(), return the price at the latest timestamp.
  5. On maximum(), iterate through all values in the hash map and return the largest.
  6. On minimum(), iterate through all values in the hash map and return the smallest.

Example Walkthrough

1update(1, 10): Store timestamp 1 → price 10
1
:
10
1/7

Code

Every time we call maximum or minimum, we scan through all n stored prices. What if we could maintain the max and min as prices are added and corrected, so that querying is O(log n) instead of O(n)?

Approach 2: Heap with Lazy Deletion

Intuition

We want max and min in O(1), and a heap gives us exactly that. A max-heap keeps the largest element on top, and a min-heap keeps the smallest. But there's a catch: when a timestamp's price gets corrected, the old price is still sitting somewhere deep inside the heap, and standard heaps don't support removing arbitrary elements efficiently.

The trick is lazy deletion. Instead of removing the stale entry, we leave it in the heap. Whenever we peek at the top, we check: "Does this entry's price still match what's in our hash map for that timestamp?" If not, the entry is stale and we pop it. We keep popping until we find a valid entry.

Algorithm

  1. Maintain a hash map mapping timestamps to their current prices.
  2. Track the latest timestamp seen.
  3. Maintain a max-heap and a min-heap, where each entry is a (price, timestamp) pair.
  4. On update(timestamp, price): update the hash map, push (price, timestamp) to both heaps, and update the latest timestamp.
  5. On current(): return the price at the latest timestamp from the hash map.
  6. On maximum(): peek at the max-heap. If the top entry's price doesn't match the hash map for that timestamp, pop it (it's stale). Repeat until the top is valid. Return the top price.
  7. On minimum(): same as maximum but with the min-heap.

Example Walkthrough

1update(1, 10): Store timestamp 1 → price 10
1
:
10
1/8

Code

The heap approach works well but accumulates stale entries. Can we do better with a data structure that handles corrections cleanly without lazy deletion?

Approach 3: Sorted Map (TreeMap / Ordered Set)

Intuition

Instead of heaps with lazy deletion, we can use a sorted data structure that maps each price to how many timestamps currently have that price. When a new price is added, we increment its count. When a correction happens, we decrement the old price's count (and remove it if the count hits zero). The max and min are always at the ends of the sorted structure.

In Java, TreeMap does this perfectly. It's a balanced BST that gives O(log n) access to the first key (minimum) and last key (maximum), plus O(log n) for insertions and deletions.

Algorithm

  1. Maintain a hash map mapping timestamps to their current prices.
  2. Maintain a sorted map (TreeMap) mapping prices to their frequency counts.
  3. Track the latest timestamp.
  4. On update(timestamp, price): if the timestamp already exists, get the old price and decrement its count in the sorted map (remove if count reaches zero). Set the new price in the hash map. Increment the new price's count in the sorted map. Update the latest timestamp.
  5. On current(): return the price at the latest timestamp.
  6. On maximum(): return the last (highest) key in the sorted map.
  7. On minimum(): return the first (lowest) key in the sorted map.

Example Walkthrough

1update(1, 10): Add price 10 with count 1
10
:
1
1/7

Code