LC 295 — Problem

Design a data structure that supports addNum(num) to insert a number and findMedian() to return the median of all numbers seen so far. Both operations must be efficient enough to be called interleaved across a large stream.

addNum(1): findMedian() returns 1
addNum(2): findMedian() returns 1.5
addNum(3): findMedian() returns 2

Constraints: `-10^5 ≤ num ≤ 10^5` · at most `5 * 10^4` calls to `addNum` and `findMedian`. Median of even count = average of two middle values; odd count = the single middle value.

Phase 1: Feel the sorted-array shift cost.

Numbers arrive one at a time. After each, you owe the caller the median so far — before the next number shows up. The obvious shot: keep them sorted and read the middle.

Tap each incoming value to drop it into its sorted slot. The counter tallies every element the array has to shift right. Even on 3 elements the waste is visible — imagine 1000.

incoming stream
739
FIG. 1 — SORTED SHELF · SHIFT COST
sorted shelfshifts: 0
Empty — tap the first incoming number to start the shelf.
— The ring marks the median slot — the only position you ever read —