Code
The highlighted line runs next. Each push/pop is shown after its sift has finished.
Why the 3 steps? Step 1 drops the number into the lower half. Step 2 hands the lower half's biggest value to the upper half, so every value in small ≤ every value in large. Step 3 moves one back if large got bigger, so small has the same size as large, or one more.
All numbers, sorted
for checking only; the heaps never sort
Cost: addNum is O(log n) (three heap operations at most), findMedian is O(1). Follow-up: if every number is in [0, 100], keep 101 counters instead and walk them to find the middle: O(1) add, O(101) find. If 99% are in that range, keep counters for 0–100 plus two small lists or heaps for the rare values outside it.
Dry-run trace
Every step as a row. Click a row to jump there.
| # | Action | Call | Detail | small (top first) | large (top first) | median |
|---|