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.