The problem
Design a structure with addNum(num) and findMedian() over a growing stream of integers.
Stuck? Reveal hints one at a time
How to approach it
- 1addNum: push onto the lower max-heap, then move its top to the upper min-heap (normalizing order).
- 2If the upper heap outgrows the lower, move its top back — sizes stay balanced with lower ≥ upper.
- 3findMedian: odd count → lower’s top; even → average of both tops.
Key insight
The push-then-transfer dance guarantees every element crosses the boundary check — you never need to compare the new number against the median explicitly.
The solution
Watch out for
- Pushing directly onto the "correct" heap by comparing with the median first invites subtle imbalance bugs — the transfer dance is safer.
- Follow-up (values in [0,100]): counting buckets beat heaps.