Find Median from Data Stream

HardHeap Design Sorting

A trading dashboard keeps showing the median price move of all trades since the market opened, and it refreshes after every trade. Moves are whole numbers of cents and can be negative. The median of a list is its middle value once sorted; when the list has an even length, it is the average of the two middle values. For example, the median of [-4, 10, 15] is 10, and the median of [-4, 10] is 3.

Implement the MedianFinder class:

MedianFinder() starts with no values.
addNum(num) records the integer num.
findMedian() returns the median of all values recorded so far, as a floating-point number.

The tests call the methods one after another, and findMedian is only called after at least one addNum. Answers within 10^-5 of the expected value are accepted.

Example 1

Input: ["MedianFinder","addNum","findMedian","addNum","addNum","findMedian","addNum","findMedian"]
[[],[12],[],[-3],[7],[],[20],[]]
Output: [null,null,12,null,null,7,null,9.5]

Explanation: With only 12 recorded, the median is 12. After -3 and 7 the sorted moves are [-3, 7, 12], so the median is 7. Adding 20 gives [-3, 7, 12, 20] and a median of (7 + 12) / 2 = 9.5.

Example 2

Input: ["MedianFinder","addNum","addNum","findMedian","addNum","addNum","findMedian"]
[[],[-8],[-2],[],[-2],[-1],[]]
Output: [null,null,null,-5,null,null,-2]

Explanation: The median of -8 and -2 is their average, -5. After -2 and -1 arrive, the sorted moves are [-8, -2, -2, -1], and both middle values are -2.

Constraints

Every recorded value fits in a 32-bit signed integer.
findMedian is called only after at least one value has been recorded.
A test makes at most 50,000 calls in total.

Follow-up: Suppose almost every price move falls between 0 and 100 cents, with only rare outliers outside that band. How could you use that to make both operations run in constant time, and how would you handle the outliers?

💡 Hint 1

Keeping a sorted array makes findMedian O(1) but each insertion O(n). You only ever need the one or two values in the middle.

💡 Hint 2

Split the numbers into a lower half and an upper half. The median depends only on the largest value of the lower half and the smallest of the upper half.

💡 Hint 3

Store the lower half in a max-heap and the upper half in a min-heap, and rebalance after each insert so the lower half has the same size as the upper half or one more. (In Java, widen to long before adding the two tops: two large ints can overflow.)

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Keep two heaps: low, a max-heap with the smaller half of the numbers, and high, a min-heap with the larger half. Maintain two invariants: every value in low is at most every value in high, and low holds either as many elements as high or exactly one more. To add a number, push it into low, then move low's maximum over to high (this keeps the halves ordered), and if high is now the bigger heap, move its minimum back. The median is then low's top when the count is odd, or the average of both tops when it is even. In Java, widen to long before adding the two tops so that values near Integer.MAX_VALUE do not overflow.

Time O(log n) per addNum, O(1) per findMedianSpace O(n)

class MedianFinder {
  constructor() {
    this.low = new Heap((a, b) => a > b); // max-heap: smaller half
    this.high = new Heap((a, b) => a < b); // min-heap: larger half
  }

  addNum(num) {
    this.low.push(num);
    this.high.push(this.low.pop());
    if (this.high.size > this.low.size) this.low.push(this.high.pop());
  }

  findMedian() {
    if (this.low.size > this.high.size) return this.low.peek();
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

// Minimal binary heap. higher(a, b) is true when a belongs closer to the top than b.
class Heap {
  constructor(higher) {
    this.items = [];
    this.higher = higher;
  }
  get size() {
    return this.items.length;
  }
  peek() {
    return this.items[0];
  }
  push(x) {
    const a = this.items;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.higher(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1;
        const r = l + 1;
        let m = i;
        if (l < a.length && this.higher(a[l], a[m])) m = l;
        if (r < a.length && this.higher(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

class MedianFinder {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // smaller half
    private final PriorityQueue<Integer> high = new PriorityQueue<>(); // larger half

    public MedianFinder() {}

    public void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) low.offer(high.poll());
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return ((long) low.peek() + high.peek()) / 2.0;
    }
}

class MedianFinder {
  constructor() {

  }

  /** @param {number} num */
  addNum(num) {

  }

  /** @return {number} */
  findMedian() {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit