51. Find Median from Data Stream

HardHeap Design Sorting

The median of a list of numbers is the middle value once the list is sorted. If the list has an even length, it is the average of the two middle values: the median of [2, 5, 9] is 5, and the median of [2, 5] is 3.5.

Design a structure that receives integers one at a time and can report the median of everything seen so far. Implement the MedianFinder class:

MedianFinder() creates an empty structure.
addNum(num) adds the integer num.
findMedian() returns the median of all numbers added so far, as a floating-point value.

Tests call the methods in sequence. findMedian is only called after at least one addNum. Answers within 10^-5 of the expected value are accepted.

Example 1

Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[5],[2],[],[9],[]]
Output: [null,null,null,3.5,null,5]

Explanation: After adding 5 and 2, the sorted list is [2, 5] with median 3.5. After adding 9 it is [2, 5, 9] with median 5.

Constraints

-2^31 <= num <= 2^31 - 1
At least one number is added before any findMedian call
At most 5 * 10^4 calls in total

Follow-up: If every number in the stream is between 0 and 100, how could you make both operations O(1)? What if 99% of them are in that range?

💡 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