Skip to main content

295. Find Median from Data Stream

hard

Design a data structure that returns the running median as numbers stream in. The two-heap trick is the canonical answer — and a frequent FAANG design question.

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

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 to the data structure; double findMedian() returns the median of all elements so far. Answers within 10^-5 of the actual answer will be accepted.

Constraints

  • -10^5 <= num <= 10^5
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 10^4 calls will be made to addNum and findMedian.

Examples

Example 1

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation: MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); medianFinder.addNum(2); medianFinder.findMedian(); // return 1.5 ((1+2)/2). medianFinder.addNum(3); medianFinder.findMedian(); // return 2.0.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Re-sorting on every findMedian is O(n log n) per query — too slow under the constraints.

Hint 2

If you could keep the lower half and the upper half separated, the median lives at the boundary.

Hint 3

Use a max-heap for the lower half and a min-heap for the upper half. Keep their sizes within 1 of each other.

Hint 4

On addNum: push to the appropriate heap, then rebalance by moving the top of the larger heap to the smaller. On findMedian: if sizes equal, average the two tops; otherwise return the top of whichever heap is larger.

Solution approach

Reveal approach

Maintain two heaps: a max-heap 'lo' for the lower half and a min-heap 'hi' for the upper half. Invariant: every element in lo <= every element in hi, and |lo| - |hi| is 0 or 1. To addNum, first push into lo, then move lo's max into hi to keep the partition correct; if hi has grown too big, move hi's min back to lo to restore the size invariant. findMedian: if lo has one more element, return lo's top; if equal, return (lo.top + hi.top) / 2. addNum is O(log n), findMedian is O(1). Total O(n) space. Follow-ups: bounded integer range (use bucketing for O(1) average) and 99th percentile rather than 50th (multiple heaps or quantile sketches like t-digest).

Complexity

Time
O(log n) per addNum, O(1) per findMedian
Space
O(n)

Related patterns

  • heap
  • two-heaps
  • design

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Bloomberg
  • Apple

Practice these live with InterviewChamp.AI

Drill Find Median from Data Stream and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →