Skip to main content

295. Find Median from Data Stream

mediumAsked at DRW

Running median over a live stream is a first-class problem at DRW: median bid-ask spread, median fill latency, median position size across strategies. The two-heap technique gives O(log n) insertion and O(1) query. DRW will ask for the Fenwick tree variant when values are bounded integers.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DRW loops.

  • Glassdoor (2026-Q1)— DRW SWE and quant developer candidates cite Find Median from Data Stream as a high-signal problem appearing in onsite rounds, often with a Fenwick tree extension.
  • Blind (2025-11)— DRW interview threads confirm this is considered a must-prepare medium, with DRW specifically testing the two-heap rebalancing invariant and the integer-bounded optimization.

Problem

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. Implement the MedianFinder class: MedianFinder() initializes the object. void addNum(int num) adds the integer num to the data structure. double findMedian() returns the median of all elements so far.

Constraints

  • −10^5 <= num <= 10^5
  • There will be at least one element before findMedian is called.
  • At most 5 × 10^4 calls will be made to addNum and findMedian.

Examples

Example 1

Input
MedianFinder(); addNum(1); addNum(2); findMedian(); addNum(3); findMedian()
Output
[null, null, null, 1.5, null, 2.0]

Explanation: After [1,2]: median = 1.5. After [1,2,3]: median = 2.

Approaches

1. Two heaps (max-heap lo + min-heap hi)

lo is a max-heap for the lower half; hi is a min-heap for the upper half. Invariants: lo.size >= hi.size and lo.size − hi.size <= 1; lo.max <= hi.min. Median is lo.top or (lo.top + hi.top) / 2.

Time
O(log n) addNum, O(1) findMedian
Space
O(n)
// JavaScript lacks a built-in heap. We simulate with sorted arrays for interview clarity.
// In production: implement a binary heap for true O(log n).
class MedianFinder {
  constructor() {
    this.lo = []; // lower half, stored descending (max at index 0)
    this.hi = []; // upper half, stored ascending (min at index 0)
  }
  _sortedInsert(arr, val, desc) {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (desc ? arr[mid] < val : arr[mid] > val) hi = mid;
      else lo = mid + 1;
    }
    arr.splice(lo, 0, val);
  }
  addNum(num) {
    this._sortedInsert(this.lo, num, true); // push to lo
    if (this.hi.length && this.lo[0] > this.hi[0]) {
      this._sortedInsert(this.hi, this.lo.shift(), false);
    }
    if (this.lo.length > this.hi.length + 1) {
      this._sortedInsert(this.hi, this.lo.shift(), false);
    } else if (this.hi.length > this.lo.length) {
      this._sortedInsert(this.lo, this.hi.shift(), true);
    }
  }
  findMedian() {
    if (this.lo.length > this.hi.length) return this.lo[0];
    return (this.lo[0] + this.hi[0]) / 2;
  }
}

Tradeoff: O(log n) per addNum with a real heap (O(n) insertion with sorted array simulation). Explain the real heap logic verbally. DRW expects the two-heap invariant proof even if JS forces a workaround.

DRW-specific tips

Explain the invariant before any code: 'lo is a max-heap of the lower half; hi is a min-heap of the upper half. Two invariants: (1) lo.size − hi.size ≤ 1, and (2) lo.max ≤ hi.min. If (2) breaks, move lo.max to hi. If (1) breaks, rebalance by moving the extremum.' DRW will then ask: 'Values are integers in [−10^5, 10^5]. How do you solve this in O(log(maxVal)) per operation?' — Fenwick tree (BIT) of length 2×10^5+1 storing cumulative counts; binary search on prefix sums to find the median rank in O(log maxVal).

Common mistakes

  • Violating the ordering invariant (lo.max > hi.min) — check and rebalance before the size invariant.
  • Allowing lo and hi to be exactly equal in size and returning lo.max only — the median is the average of both tops when sizes are equal.
  • In JS, using sort() on each insertion — O(n log n) per addNum, not O(log n).
  • Not handling the odd vs even count correctly in findMedian.

Follow-up questions

An interviewer at DRW may pivot to one of these next:

  • Sliding Window Median (LC 480) — rolling window of size k; must also efficiently remove the outgoing element.
  • How do you compute the running median using a Fenwick tree for integer-bounded input?
  • What is the expected median of n i.i.d. uniform [0, 1] random variables as n → ∞?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why max-heap for the lower half?

You need instant O(1) access to the largest element of the lower half to compute the median. A max-heap's root gives this.

Does the order of invariant checks matter?

Yes — check ordering (lo.max ≤ hi.min) first, then size. Doing size rebalancing before ordering can move a value to the wrong heap.

When is the Fenwick tree preferred?

When values are bounded integers (as in this problem) and you need O(log maxVal) per operation regardless of n. The two-heap approach is O(log n), which is better for large n with small value ranges.

Practice these live with InterviewChamp.AI

Drill Find Median from Data Stream and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →