Split elements into two balanced groups using a max-heap and a min-heap to track the running median in O(log n) per insertion.
The two heaps pattern maintains two heaps that together partition a stream of numbers into a lower half and an upper half. A max-heap stores the smaller half (so we can quickly access the largest of the small numbers), and a min-heap stores the larger half (so we can quickly access the smallest of the large numbers). The median is always at the top of one or both heaps.
We keep two heaps balanced so their sizes differ by at most 1. The max-heap top and min-heap top are always the two middle elements. The median is either one of them or their average.
Why two heaps? A single sorted array would need O(n) to insert. A balanced BST would give O(log n) but is complex. Two heaps give us O(log n) insertion and O(1) median retrieval with a simple, elegant invariant: max-heap.size() == min-heap.size() or max-heap.size() == min-heap.size() + 1.
Look for these recognition signals in the problem statement. If you spot one, the two heaps pattern is very likely the intended approach.
"Find the median" or "running median"
"Balance two groups" or "partition into halves"
"Sliding window median" or "rolling percentile"
"Maximize minimum" or "schedule with profit/capital"
The key clue: You need to repeatedly access the middle element(s) of a dynamic collection. A brute-force sort after each insertion is O(n log n). Two heaps reduce each insertion to O(log n) and each median query to O(1).
The most direct application of two heaps. We maintain a max-heap for the lower half and a min-heap for the upper half. After each insertion, we rebalance so the heaps differ in size by at most 1.
Watch the two heaps grow and rebalance after each number.
Extend the two heaps pattern with lazy deletion. When the window slides, we add the new element and mark the outgoing element for removal. We only physically remove elements from a heap when they appear at the top. This avoids O(n) removal costs.
Sliding window of size 3. For each window, report the median.
Lazy deletion trick: Instead of searching the heap for the outgoing element (O(n)), we keep a hash map of "pending deletions." When the top of a heap matches a pending deletion, we pop and decrement the count. This keeps each operation at O(log n) amortized.
Here is the annotated Java template for the two heaps pattern applied to "Find Median from Data Stream."
// Two Heaps: Find Median from Data Stream class MedianFinder { // max-heap for the lower half PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // min-heap for the upper half PriorityQueue<Integer> hi = new PriorityQueue<>(); void addNum(int num) { lo.offer(num); // always add to max-heap first hi.offer(lo.poll()); // move max of lower to upper if (lo.size() < hi.size()) { // keep lo.size ≥ hi.size lo.offer(hi.poll()); } } double findMedian() { if (lo.size() > hi.size()) { return lo.peek(); // odd count: median is max-heap top } return (lo.peek() + hi.peek()) / 2.0; // even: average of both tops } }
// Ensure heaps are balanced after any add/remove void rebalance() { if (lo.size() > hi.size() + 1) { hi.offer(lo.poll()); // move max of lower to upper } else if (hi.size() > lo.size()) { lo.offer(hi.poll()); // move min of upper to lower } }
The "add-then-rebalance" trick: Always insert into the max-heap first, then immediately move its top to the min-heap. Then, if the min-heap is larger, move its top back. This elegant 3-line logic guarantees both the ordering invariant (all elements in lo ≤ all elements in hi) and the size invariant (lo.size ≥ hi.size, difference ≤ 1).
Let us trace through a larger example, showing both heaps and the median at every stage.
After each insertion, the median updates.
| INSERT | MAX-HEAP (lower) | MIN-HEAP (upper) | MEDIAN |
|---|---|---|---|
| 6 | [6] | [] | 6 |
| 2 | [2] | [6] | 4 |
| 10 | [6, 2] | [10] | 6 |
| 3 | [3, 2] | [6, 10] | 4.5 |
| 7 | [6, 3, 2] | [7, 10] | 6 |
| 1 | [3, 2, 1] | [6, 7, 10] | 4.5 |
Notice the invariant: After every insertion, every element in the max-heap is ≤ every element in the min-heap. The two heap tops are always the two middle elements of the sorted order. This is maintained automatically by the "add to lo, move top to hi, rebalance" procedure.
These are the classic LeetCode problems that use the two heaps pattern, listed in rough order of difficulty.
Practice tip: Start with #295 (the pure two heaps template). Then tackle #480 which adds the sliding window + lazy deletion complexity. For a different flavor, try #502 (IPO) where the two heaps represent "available projects" and "affordable projects" — the same split-and-pick-best idea applied to a greedy optimization.
Enter numbers one at a time or provide a list. Watch each number get distributed between the max-heap (lower half) and min-heap (upper half), with the running median displayed after each insertion.
Each insertion involves at most 3 heap operations: one offer to the max-heap, one poll + offer to the min-heap, and potentially one more poll + offer to rebalance. Each heap operation on a heap of size n/2 is O(log n).
Finding the median is O(1) because it only requires peeking at the top of one or both heaps.
Space: Both heaps together store all n elements, so space is O(n).
For the sliding window median (#480), each window step involves an add and a remove. With lazy deletion, the amortized cost per window step is O(log k) where k is the window size. Total time for an array of length n: O(n log k).
Comparison with alternatives: A sorted array gives O(1) median but O(n) insertion. A balanced BST (like a red-black tree) gives O(log n) for both but is far more complex to implement. Two heaps hit the sweet spot: O(log n) insertion, O(1) median, and the code is simple enough to write in an interview.
Max-heap for lower half, min-heap for upper half. This is the fundamental split. The max-heap top is the largest small element, and the min-heap top is the smallest large element. Together they frame the median.
Keep sizes balanced within 1. After every insertion, rebalance so that the max-heap has either the same number of elements as the min-heap (even total) or exactly one more (odd total). This invariant is what makes O(1) median work.
The "add, move, rebalance" 3-step is your template. Always add to the max-heap first, move its top to the min-heap, then move back if needed. This 3-line procedure maintains both the ordering and size invariants automatically.
Lazy deletion for sliding windows. When elements leave the window, mark them for lazy deletion instead of searching the heap. Clean up lazily when a marked element reaches the top. This keeps the sliding window variant at O(log k) per step.
The pattern extends beyond medians. The same two-heap idea applies to problems like IPO (#502), where one heap holds available options and the other holds filtered candidates. Whenever you need to repeatedly pick the best from a dynamically partitioned collection, think two heaps.