The Runtime Theory
hardLeetCode#two-heaps#streaming

Find Median from Data Stream

Design a structure that accepts numbers one at a time and reports the median of all values seen.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

inadd(1), add(2), median(), add(3), median()

out[1.5,2.0]

inadd(-1), median()

out[-1.0]

inadd(5), add(5), median()

out[5.0]

Design a structure that accepts numbers one at a time and reports the median of all values seen.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain the time and space complexity in terms of the input sizes and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs covered by the contract.

Reasoning prompt

Keep a max-heap for the lower half and min-heap for the upper half. Maintain size balance and ordering after each insertion.

Use the linked judge for the canonical problem. The examples above are compact TRT checks; write additional cases before submitting, especially for the boundary that tends to break your chosen invariant.

More practice in this topic

medium · heapK Closest Points to Originmedium · heapFind K Pairs with Smallest Sumsmedium · heapKth Largest Element in an Array

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save