Skip to main content

295. Find Median from Data Stream

hardAsked at Duolingo

Maintain a running median as integers arrive one at a time using two heaps — the same dual-priority-queue structure Duolingo's spaced-repetition scheduler uses to track the median session-difficulty score across an evolving stream of lesson completions.

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

Problem

Design a class MedianFinder that supports two operations: addNum(num) adds an integer from a data stream to the data structure; findMedian() returns the median of all elements added so far. If the total number of elements is even, the median is the average of the two middle values.

Constraints

  • -10^5 <= num <= 10^5
  • At most 5 * 10^4 calls will be made to addNum and findMedian
  • findMedian will be called at least once

Examples

Example 1

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

Explanation: After [1,2] median = (1+2)/2 = 1.5; after [1,2,3] median = 2.

Approaches

1. Brute force — sorted array

Keep all numbers in a sorted array; insertions are O(n) and median reads are O(1).

Time
O(n) addNum, O(1) findMedian
Space
O(n)
class MedianFinder {
  constructor() {
    this.data = [];
  }

  addNum(num) {
    let lo = 0;
    let hi = this.data.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.data[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    this.data.splice(lo, 0, num);
  }

  findMedian() {
    const n = this.data.length;
    const mid = Math.floor(n / 2);
    return n % 2 === 1
      ? this.data[mid]
      : (this.data[mid - 1] + this.data[mid]) / 2;
  }
}

Tradeoff:

2. Optimal — two heaps (max-heap lo + min-heap hi)

Maintain a max-heap for the lower half and a min-heap for the upper half, keeping sizes balanced; addNum is O(log n), findMedian is O(1).

Time
O(log n) addNum, O(1) findMedian
Space
O(n)
// JavaScript lacks a native heap; implement a MinHeap used as both min and max (via negation).
class MinHeap {
  constructor() { this.h = []; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p] <= this.h[i]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      while (true) {
        let s = i;
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        if (l < this.h.length && this.h[l] < this.h[s]) s = l;
        if (r < this.h.length && this.h[r] < this.h[s]) s = r;
        if (s === i) break;
        [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
        i = s;
      }
    }
    return top;
  }
  peek() { return this.h[0]; }
  size() { return this.h.length; }
}

class MedianFinder {
  constructor() {
    this.lo = new MinHeap(); // max-heap via negation: stores lower half
    this.hi = new MinHeap(); // min-heap: stores upper half
  }

  addNum(num) {
    this.lo.push(-num);
    this.hi.push(-this.lo.pop());
    if (this.hi.size() > this.lo.size()) {
      this.lo.push(-this.hi.pop());
    }
  }

  findMedian() {
    if (this.lo.size() > this.hi.size()) return -this.lo.peek();
    return (-this.lo.peek() + this.hi.peek()) / 2;
  }
}

Tradeoff:

Duolingo-specific tips

Duolingo's difficulty rating engine streams lesson-performance scores and needs the median at any point to calibrate the next challenge level — textbook two-heap territory. JavaScript has no built-in heap, so interviewers pay close attention to whether you can implement one cleanly or at least describe the interface correctly. The negation trick (store negative values in a MinHeap to simulate a MaxHeap) is the standard workaround; explain it explicitly before coding. A follow-up often asked: 'If 99% of values fall in [0,100], can you optimize?' — answer: fixed-size bucket array with two running pointers.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →