Two Heaps¶
Also known as: Median Maintenance, Max-Heap + Min-Heap
Split the data into a lower half (max-heap) and an upper half (min-heap), kept balanced in size. The two heap tops sit exactly at the middle of the data, so the median is always one glance away, no matter how much data streams in.
Before you start¶
What 'solved properly' looks like
Target: O(log n) per insertion, O(1) to read the median. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You maintain two heaps: a max-heap for the lower half of the data and a min-heap for the upper half. Every new number goes into one heap or the other, then you rebalance so the sizes differ by at most one. The median is always either the top of the larger heap or the average of both tops. The invariant must be restored after every single insertion — a one-element imbalance silently drifts the median wrong.
Why it matters: It's the clearest example of choosing a data structure to make a hard question trivial, rather than choosing a cleverer algorithm. The median-of-a-stream problem looks impossible until you see this split, and then it looks trivial.
When to reach for it¶
Reach for it when you need the median of a data stream, or any problem that involves continuously balancing two halves of data against each other.
When not to use it
The heaps must be rebalanced after every single insertion or the median silently drifts wrong. And if the dataset is static, this is heavy machinery for nothing — just sort once. Note: this pattern has fewer good free problems than most. The canonical problem below is Hard, and the alternatives are also Hard — that's honest, not a gap.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Find Median from Data Stream | LeetCode | Hard | 35 mins | teaching |
| 2 | IPO | LeetCode | Hard | 40 mins | challenge |
Already know this? Test out.
If you can solve IPO cleanly in one sitting — using two heaps to manage the capital and profit constraints — you already own this pattern, so move on to the next one. Note this one is Hard and that's expected; if it doesn't come easily, work the set from the top.