Top-K and Streaming
What is this?
Sometimes you only care about the few best items out of a huge pile, or values keep arriving over time and you need the current winner on demand. Instead of sorting everything, you keep a small heap that holds only the best candidates and let the rest fall away. The most important item is always sitting right at the top, ready to grab.
💡 Fun fact: Streaming services and search engines use this exact trick to surface your top results without ever sorting the millions of items they did not show you.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: When you only care about the K best elements, you don't need to sort everything — you maintain a heap of size K and let the extreme leak out. When data streams in and you must answer min/max on demand, heaps give you the extremes in O(log n), and a small auxiliary map handles the awkward part: knowing which heap entries are still valid.
The pattern
A heap shines when the full dataset is large but the answer depends on only a handful of elements, or when values arrive over time and you need the running extreme.
- For top-K, keep a heap of size K. Push each element; if the heap grows past K, pop the worst. What survives is the answer — in O(n log K) instead of O(n log n).
- For streaming, a heap holds candidates for the current min/max, but stale entries pile up. Pair the heap with a timestamp map and lazily discard any popped entry that no longer matches the latest value.
The problems
- K Closest Points to Origin — keep a size-K max-heap keyed by distance. Push each point; once the heap exceeds K, pop the farthest. The K points left are the closest. The max-heap lets you evict the current worst in one step.
- Stock Price Fluctuation — maintain a max-heap and a min-heap of
(price, timestamp)plus a map from timestamp to the latest price. On a query, pop the heap top while its price disagrees with the map (a corrected record); the first valid top is the true current max or min.
Key takeaways
- Size-K heap for top-K — bound the heap, evict the worst, get O(n log K).
- Max-heap to keep the K smallest (and min-heap to keep the K largest) — the extreme you pop is the one you want gone.
- Heaps + freshness map for streams — heaps can't update in place, so mark entries stale and discard lazily on pop.
- Lazy deletion beats rebuilding the heap on every change.
- Why interviewers love it: it tests whether you reach for the bounded heap instead of sorting the whole input.
Order: K Closest Points to Origin → Stock Price Fluctuation.
Stock Price Fluctuation
Core idea: The data is a stream of corrections — a price you recorded earlier can be fixed later. So one structure must be the single source of truth (a
dictfrom timestamp to price), and the heaps that answermaximum()/minimum()are allowed to hold stale entries. You never hunt down and delete the old value; you just ignore any heap entry whose price no longer matches the dict the moment it surfaces on top. That's lazy deletion.
Problem, rephrased
Forget the textbook phrasing. Here's the scenario:
You're building the price feed for a trading dashboard. Trades arrive over the wire tagged with a timestamp and a price. The catch: the feed is noisy, so an exchange can send a correction — the same timestamp shows up again with a fixed price ("ignore what I told you at t=4, the real price was 5, not 3"). Your dashboard has to answer four questions instantly at any moment:
update(timestamp, price)— record a price, or correct a price you were told earlier for that same timestamp.current()— the price at the latest timestamp seen so far (the most recent trade, not the largest price).maximum()— the highest correct price across all timestamps right now.minimum()— the lowest correct price across all timestamps right now.
"Latest" means largest timestamp, not most-recently-called. And every answer must reflect corrections: once t=4 is fixed to 5, the old 3 must never influence maximum()/minimum() again.
Here is a single run, in order, with what each query returns:
| Operation | Effect on state | current() |
maximum() |
minimum() |
|---|---|---|---|---|
update(1, 10) |
t=1 → 10 |
10 |
10 |
10 |
update(2, 5) |
t=2 → 5 |
5 |
10 |
5 |
current() |
latest timestamp is 2 |
5 |
— | — |
maximum() |
best price is 10 |
— | 10 |
— |
update(1, 3) |
correction: t=1 fixed 10 → 3 |
5 |
5 |
3 |
maximum() |
old 10 is now stale; best is 5 |
— | 5 |
— |
minimum() |
lowest is the corrected 3 |
— | — | 3 |
The update(1, 3) line is the whole problem in miniature: a value already inside both heaps just became wrong, and maximum() must drop from 10 to 5 without us ever physically finding and removing the old 10.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson