Two Heaps
Split the data into a max heap of the lower half and a min heap of the upper half, rebalancing so their sizes differ by at most one.
Heap / Priority QueueO(log n) per insert, O(1) queryNew2 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
median of a stream
sliding window median
balanced partition of a stream
The template
Get this into muscle memory, then adapt the condition per problem.
if (lo.isEmpty() || x <= lo.peek()) lo.push(x); else hi.push(x); if (lo.size > hi.size + 1) hi.push(lo.pop()); else if (hi.size > lo.size) lo.push(hi.pop());
If you are stuck
The generic hint ladder for this pattern, in order.
- 1The median only depends on the middle, not the full order.
- 2Keep the smaller half and the larger half separately.
- 3Rebalance after every insertion so the tops stay adjacent to the median.
Drill it
Every problem in the bank that uses this pattern.
0 / 2 solved