Streaming and Medians

What is this?

Numbers arrive one at a time and never stop, and after each one you must report the median. You cannot sort — that is O(n log n) per arrival. You cannot keep an ordered list — insertion is O(n). What you can do is notice that the median only depends on the boundary between the smaller half and the larger half, and keep the two halves in separate heaps that face each other across that boundary.

The lower half's largest value and the upper half's smallest value sit at the two tops. The median is one of them, or their average.

💡 Fun fact: the standard two-heap insertion looks wasteful — every arrival is pushed into one heap, immediately moved to the other, and sometimes moved back. That shuffle is deliberate: it guarantees both invariants at once (every value in the lower half ≤ every value in the upper half, and the sizes differ by at most one) without any case analysis on where the new value belongs. Three unconditional heap operations replace a thicket of comparisons, and they are still O(log n).

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: over a stream you cannot keep everything, so keep only what determines the answer — the two elements straddling a partition, or the single best next move. Both are heap tops, and both survive updates in O(log n).

1. Two heaps, three operations

import heapq

lower, upper = [], []          # lower is a max-heap (negated), upper is a min-heap

def add(num):
    heapq.heappush(lower, -num)                      # 1. always into the lower half
    heapq.heappush(upper, -heapq.heappop(lower))     # 2. hand its largest to the upper half
    if len(upper) > len(lower):                      # 3. rebalance if the upper grew too big
        heapq.heappush(lower, -heapq.heappop(upper))

def median():
    if len(lower) > len(upper):
        return -lower[0]                             # odd count → the extra element
    return (-lower[0] + upper[0]) / 2                # even count → the average of both tops

Step 2 is what enforces the ordering property. By pushing into lower and immediately moving its maximum across, any value that belongs above the boundary migrates there automatically — no comparison with the current median required.

The convention here is that lower may hold one extra element, so an odd-length stream reads its median directly from lower[0]. Pick a convention and be consistent; mixing them is the usual source of off-by-one errors.

2. A score that changes when you use it

Maximum Average Pass Ratio is a different streaming shape. Each class has a pass ratio, and adding a guaranteed-passing student improves it by a computable marginal gain. Push every class keyed on that gain, then repeatedly: pop the largest gain, apply the student, recompute the class's new gain, and push it back.

The greedy is valid because the gain function is decreasing — each student added to a class helps less than the last. That property is what stops an early choice from being regretted later, and it is worth stating explicitly rather than assuming.

gain(pass, total) = (pass + 1)/(total + 1) - pass/total

3. A 30-second worked example (running median)

add 5   lower=[5]        upper=[]         median = 5
add 15  lower=[5]        upper=[15]       median = (5+15)/2 = 10
add 1   lower=[5,1]      upper=[15]       median = 5
add 3   lower=[3,1]      upper=[5,15]     median = (3+5)/2 = 4

Check the last one by hand: the values are 1, 3, 5, 15, so the median is (3+5)/2 = 4 ✓. Notice 5 migrated from the lower half to the upper half when 3 arrived — the shuffle did that automatically, with no comparison written by hand.

4. Where you'll actually meet this

• Latency monitoring. Running p50 over a request stream, updated per request rather than recomputed per window.
• Financial tick data. Median price over a rolling window, where re-sorting per tick is unaffordable.
• Sensor and IoT pipelines. Median filtering to reject outliers in real time on constrained hardware.
• A/B testing dashboards. Live median session metrics as events stream in.
• Resource allocation. The marginal-gain heap is how greedy budget allocation works — spend the next unit wherever it buys the most.

5. Problems in this chapter

▶ Find Median from Data Stream

Support addNum and findMedian over an unbounded stream. Two heaps straddling the boundary, rebalanced after every insertion.
Pattern: two heaps across a partition. Target: O(log n) insert, O(1) query.

▶ Maximum Average Pass Ratio

Distribute extraStudents across classes to maximise the average pass ratio. A max-heap keyed on marginal gain; recompute and re-push after each assignment.
Pattern: greedy by marginal gain, with re-push. Target: O((n + k) log n) time, O(n) space.

6. Common pitfalls 🚫

• Forgetting to negate for the max-heap. Python's heapq is min-only, and a missing sign flips the whole structure silently.
• Inconsistent size convention. Decide which heap may hold the extra element and never deviate; the median formula depends on it.
• Comparing against the current median to place a value. The push-then-move shuffle removes that decision entirely — do not reintroduce it.
• Integer division on the average. (a + b) / 2 must be floating point; // silently truncates.
• Sorting the classes once in the pass-ratio problem. Priorities change after each assignment, so the heap must be re-pushed, not pre-sorted.
• Comparing ratios as floats when ties matter. Cross-multiplying is safer where precision is tight.
• Assuming the greedy is obvious. State that marginal gain decreases — that is the proof, and it is exactly what an interviewer will probe.

7. Key takeaways

1. Store only what determines the answer. For a median that is two elements; for a greedy it is one.
2. Two heaps straddle a partition and give O(1) reads with O(log n) updates.
3. Push, move, rebalance — three unconditional operations beat a pile of conditionals.
4. Re-push when priority changes. A used item with a new score is simply a fresh insertion.
5. Decreasing marginal gain is what makes the greedy safe. Say it out loud.
6. Pick a size convention and hold it. Most bugs here are off-by-one, not algorithmic.
7. Why interviewers love it: it is a design question with an obvious wrong answer (keep a sorted list) and a clean right one, and the follow-ups — memory bounds, duplicate handling, removal — go as deep as they like.

Order: Find Median from Data Stream → Maximum Average Pass Ratio.