Skip to main content

23. Find Median from Data Stream

hardAsked at Intuit

Design a data structure that supports adding integers and returning the running median in O(log n) add and O(1) median. Intuit asks this for senior coding rounds, framing it as 'running median of daily transaction amounts in QuickBooks.'

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit SWE III onsite — two-heap design under the 'running transaction median' framing.
  • LeetCode Discuss (2025-10)— Intuit senior loop — interviewer asked about thread safety as a follow-up.

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 from the data stream; double findMedian() returns the median of all elements so far. Answers within 10^-5 are accepted.

Constraints

  • -10^5 <= num <= 10^5
  • There will be at least one element in the data stream before findMedian().
  • At most 5 * 10^4 calls.

Examples

Example 1

Input
addNum(1); addNum(2); findMedian(); addNum(3); findMedian();
Output
1.5, 2.0

Approaches

1. Sorted array

Maintain a sorted array. addNum is O(n) for insert; findMedian is O(1) by indexing the middle.

Time
O(n) add, O(1) findMedian
Space
O(n)
class MedianFinder {
  constructor() { this.arr = []; }
  addNum(num) {
    let lo = 0, hi = this.arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.arr[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    this.arr.splice(lo, 0, num);
  }
  findMedian() {
    const n = this.arr.length;
    return n % 2 ? this.arr[n >> 1] : (this.arr[n / 2 - 1] + this.arr[n / 2]) / 2;
  }
}

Tradeoff: O(n) per add — splice shifts elements. Fails on n=50k with 10^4 inserts in tight loops.

2. Two heaps (max-heap of low half, min-heap of high half)

Keep the lower half in a max-heap and the upper half in a min-heap. Balance so sizes differ by at most 1. Median = top of larger heap, or average of both tops when sizes are equal.

Time
O(log n) add, O(1) findMedian
Space
O(n)
class MaxHeap {
  constructor() { this.h = []; }
  push(v) { this.h.push(v); this._up(this.h.length - 1); }
  pop() { const t = this.h[0]; const last = this.h.pop(); if (this.h.length) { this.h[0] = last; this._down(0); } return t; }
  top() { return this.h[0]; }
  size() { return this.h.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.h[p] < this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; } else break; } }
  _down(i) { const n = this.h.length; while (true) { const l = 2*i+1, r = 2*i+2; let b = i; if (l < n && this.h[l] > this.h[b]) b = l; if (r < n && this.h[r] > this.h[b]) b = r; if (b === i) break; [this.h[b], this.h[i]] = [this.h[i], this.h[b]]; i = b; } }
}
class MinHeap extends MaxHeap {
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.h[p] > this.h[i]) { [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p; } else break; } }
  _down(i) { const n = this.h.length; while (true) { const l = 2*i+1, r = 2*i+2; let b = i; if (l < n && this.h[l] < this.h[b]) b = l; if (r < n && this.h[r] < this.h[b]) b = r; if (b === i) break; [this.h[b], this.h[i]] = [this.h[i], this.h[b]]; i = b; } }
}
class MedianFinder {
  constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
  addNum(num) {
    if (this.lo.size() === 0 || num <= this.lo.top()) this.lo.push(num);
    else this.hi.push(num);
    if (this.lo.size() > this.hi.size() + 1) this.hi.push(this.lo.pop());
    else if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
  }
  findMedian() {
    if (this.lo.size() > this.hi.size()) return this.lo.top();
    return (this.lo.top() + this.hi.top()) / 2;
  }
}

Tradeoff: O(log n) add, O(1) findMedian. The two-heap invariant: lo.size === hi.size OR lo.size === hi.size + 1.

Intuit-specific tips

Intuit cares about this for QuickBooks reports — daily/weekly/monthly running medians of transactions. They grade for the heap-invariant statement upfront ('lo.size === hi.size OR lo.size === hi.size + 1') and whether you reach for integer arithmetic for the average ((a + b) / 2 — but for cents, use (a + b) without dividing, or shift by 2 only at display time). Bonus signal: discuss thread safety (the toy version isn't safe; production needs a mutex around addNum).

Common mistakes

  • Letting the heap sizes diverge by 2 — invariant must be enforced after every add.
  • Computing the average as (a + b) / 2 with floats when both are cent integers — minor precision loss; consider returning a tuple (sum, count) for display logic.
  • Forgetting to handle the empty-stream case in findMedian.

Follow-up questions

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

  • Sliding-window median (LC 480).
  • What if numbers can be removed too? (Use a lazy-deletion heap or order-statistic tree.)
  • How would you parallelize across multiple input streams?

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 two heaps instead of a sorted set?

JS doesn't ship an order-statistic tree, and a sorted array is O(n) on insert. Two heaps give O(log n) insert and O(1) median, which is the optimal achievable without a balanced BST.

How would you handle financial values (cents)?

Store cents as integers and compute the average as (lo.top() + hi.top()). If the caller wants dollars, divide by 100 at the display boundary. Never divide intermediate ledger values.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →