Hints — p43 Find Median from Data Stream

Hint 1. Median lives at the BOUNDARY between the smaller and larger halves. If you can maintain those two halves with O(log n) updates, you can read the median in O(1).

Hint 2. Use TWO heaps:

  • lo — max-heap of the smaller half (Python: store as negatives).
  • hi — min-heap of the larger half.

Median = top of lo (odd) or avg of tops (even).

Hint 3. Two invariants to maintain:

  1. Sizes: |lo| ∈ {|hi|, |hi| + 1} (let lo hold the extra when total is odd).
  2. Order: every element of lo ≤ every element of hi.

State these BEFORE writing addNum.

Hint 4. Canonical addNum — the “lo-then-move-then-rebalance” dance:

heappush(lo, -num)                  # always start in lo
heappush(hi, -heappop(lo))          # move lo's max to hi (preserves order invariant)
if len(hi) > len(lo):
    heappush(lo, -heappop(hi))      # restore size invariant

Three pushes, all O(log n). Bug-resistant because invariants are preserved one at a time.

Hint 5. Median:

if len(lo) > len(hi): return float(-lo[0])
return (-lo[0] + hi[0]) / 2.0

Follow-up to think about: how would you support REMOVAL (sliding-window median, LC 480)? Lazy deletion with a deleted_count dict.

If still stuck: see solution.py.