The problem
Return the median of every size-k window as it slides over the array.
Stuck? Reveal hints one at a time
How to approach it
- 1Maintain lower (max-heap) and upper (min-heap) with a balance counter that only counts LIVE elements.
- 2On slide: add the incoming number to the correct heap; mark the outgoing number in a delayed-deletion map, adjusting the balance.
- 3Rebalance by moving tops when the live-count difference exceeds 1.
- 4Before reading a median, pop any heap top that appears in the deletion map.
Key insight
Heaps cannot delete from the middle — but they never need to: a dead element only matters when it surfaces at the top, so purge lazily at read time.
The solution
Watch out for
- Balance counters must track LIVE elements only — heap.length lies once lazy deletions accumulate.
- Negative zeros and integer overflow on (a+b)/2 bite in some languages; Python floats sidestep both.