Start learning free

LESSON 458 OF 671 · HEAP

Find Median From Data Stream in Java: Two Heaps, O(log n) Adds

Practice O(log n) Read the full explanation

The median of a list of numbers is the middle value once the list is sorted. When the list has an even number of values, there is no single middle value, and the median is the mean of the two middle values:

  • the median of [2, 3, 4] is 3;
  • the median of [2, 3] is (2 + 3) / 2 = 2.5.

Numbers arrive one at a time, and at any moment you may be asked for the median of all the numbers that have arrived so far. Implement the class MedianFinder:

  • MedianFinder() creates an object that holds no numbers yet.
  • addNum(num) adds the integer num to the numbers seen so far.
  • findMedian() returns the median of all the numbers added so far.

The input is a list of operations, applied in order to one new MedianFinder. The output lists what the findMedian calls return, in order, each printed with one digit after the decimal point (2.0, 2.5). The starter code spells these names the way your language does.

 

Example 1:

Input:
    addNum(1)
    addNum(2)
    findMedian()
    addNum(3)
    findMedian()
Output: 1.5 2.0
Explanation:
After 1 and 2, there are two middle values, so the median is (1 + 2) / 2 = 1.5.
After 3 arrives, the sorted numbers are [1, 2, 3], and the middle one is 2.

Example 2:

Input:
    addNum(5)
    findMedian()
    addNum(-3)
    findMedian()
    addNum(-3)
    findMedian()
    addNum(10)
    findMedian()
Output: 5.0 1.0 -3.0 1.0
Explanation:
[5] has the median 5. [-3, 5] has the median (-3 + 5) / 2 = 1.
[-3, -3, 5] has the median -3: a number that arrives twice counts twice.
[-3, -3, 5, 10] has the median (-3 + 5) / 2 = 1.

Example 3:

Input:
    addNum(4)
    addNum(3)
    findMedian()
    findMedian()
    addNum(2)
    addNum(1)
    findMedian()
Output: 3.5 3.5 2.5
Explanation: The numbers don't arrive in sorted order, and asking twice in a row gives the same answer, because findMedian changes nothing. At the end the sorted numbers are [1, 2, 3, 4], so the median is (2 + 3) / 2 = 2.5.

 

Constraints:

  • -105 <= num <= 105
  • findMedian is called only after at least one call to addNum.
  • At most 5 * 105 calls in total are made to addNum and findMedian.

Note:

addNum should run in O(log n) time and findMedian in O(1) time, where n is the number of values added so far.

STEP 1 OF 7
    Ctrl + Enter to check

    JAVA · HEAP

    Find Median From Data Stream in Java, explained

    Problem overview

    The class MedianFinder receives integers one at a time through addNum(int num) and, at any moment, must answer findMedian() with the median of everything added so far, as a double. The median is the middle value of the sorted numbers; with an even count it is the mean of the two middle values.

    After adding 1 and 2, the median is 1.5. After adding 3, the sorted numbers are [1, 2, 3] and the median is 2.0. Numbers can repeat and arrive in any order: adding 5, -3, -3 and then 10 gives medians 5.0, 1.0, -3.0 and 1.0.

    The lesson asks for addNum in O(log n) time and findMedian in O(1).

    Approach: keep the two halves in two heaps

    The simple approach stores every number in a list and sorts it for each question, which costs O(n log n) per findMedian. Keeping the list sorted at all times is no better, because inserting into the middle of an array shifts elements.

    The median only depends on the middle one or two values, so the class never needs the whole list in order. It splits the numbers into two halves:

    • low, a max-heap holding the smaller half. Its top is the largest value of that half.
    • high, a min-heap holding the larger half. Its top is the smallest value of that half.

    Every value in low is at most every value in high, so the two middle values of the sorted numbers are exactly the two tops. The class keeps the halves balanced: they are the same size, or low has one more. Then the median is the top of low when the count is odd, and the mean of the two tops when it is even. Reading a top is O(1), and each insertion or removal on a heap is O(log n).

    Step by step

    1. Declare low as a PriorityQueue<Integer> with the comparator (x, y) -> y - x. Java's PriorityQueue is a min-heap, and this comparator reverses the order, so the largest value comes out first.
    2. Declare high as a plain PriorityQueue<Integer>, a min-heap.
    3. In addNum, add num to low first. Every new number goes through the lower half.
    4. Move the top of low to high with high.add(low.poll()). poll() removes and returns the largest value of low. Whatever num was, this moves the largest of the lower half upward, which keeps every value in high at least every value in low. If num was small, it stays in low and a larger value moves up instead.
    5. Rebalance. If high is now bigger than low, move the top of high back to low. After this, the sizes are equal or low is one larger.
    6. In findMedian, handle an odd count. If low is larger, return low.peek(), which reads the top without removing it. The Integer becomes a double automatically.
    7. Otherwise the halves are equal, so return the two tops added together and divided by 2.0.

    The solution in Java

    class MedianFinder {
        PriorityQueue<Integer> low = new PriorityQueue<>((x, y) -> y - x);
        PriorityQueue<Integer> high = new PriorityQueue<>();
    
        public void addNum(int num) {
            low.add(num);
            high.add(low.poll());
            if (high.size() > low.size()) {
                low.add(high.poll());
            }
        }
    
        public double findMedian() {
            if (low.size() > high.size()) {
                return low.peek();
            }
            return (low.peek() + high.peek()) / 2.0;
        }
    }
    

    A short walk through the code, with values from a real run: after addNum(7), low holds [7] and high is empty. After addNum(1), the top of low is 1 and the top of high is 7, with one value in each. After addNum(9), the top of low is 7 and the top of high is 9, with sizes 2 and 1, and findMedian() returns 7.0.

    Java details worth understanding:

    • PriorityQueue lives in java.util. In a file of your own, add import java.util.PriorityQueue; or import java.util.*;.
    • Integer division. 3 / 2 is 1 in Java, while 3 / 2.0 is 1.5. Dividing the sum by 2.0 keeps the half.
    • The comparator (x, y) -> y - x can overflow for values far apart: Integer.MIN_VALUE - 1 wraps to 2147483647. Here the numbers stay between -100,000 and 100,000, so it is safe. For arbitrary int values, use Collections.reverseOrder() or (x, y) -> Integer.compare(y, x).
    • The sum of the two tops can't overflow here. low.peek() + high.peek() adds two Integers as ints before the division, which is fine for this lesson's range. With values near Integer.MAX_VALUE it would wrap, and the fix is to add as double or long.
    • peek() returns null on an empty heap, and unboxing that null throws a NullPointerException. The lesson only calls findMedian after at least one addNum.

    Complexity

    addNum: O(log n). It does at most three heap insertions and two removals of the top, each O(log n).

    findMedian: O(1). It reads one or two tops.

    Space: O(n). Every number is stored in exactly one heap.

    Edge cases and common mistakes

    • A single number. After addNum(5), low has one value and high none, so findMedian() returns 5.0.
    • Duplicates. Both -3s count: after 5, -3, -3 the median is -3.0.
    • Asking twice. findMedian only reads the tops, so repeated calls give the same answer. With 4 and 3 added, it returns 3.5 both times.
    • Dividing by 2 instead of 2.0. The sum of two ints divided by the int 2 truncates, so a median of 2.5 would come out as 2.
    • Wrong heap direction. A default PriorityQueue for low would put the smallest value on top, and the middle would be wrong.
    • Skipping the rebalance. Without it, one heap can grow far larger than the other and the tops are no longer the middle values.

    Testing

    • Add 1, 2, ask, add 3, ask: 1.5, then 2.0.
    • Add 5, ask, add -3, ask, add -3, ask, add 10, ask: 5.0, 1.0, -3.0, 1.0.
    • Add 4, 3, ask twice, add 2, 1, ask: 3.5, 3.5, 2.5.
    Keep going with Java650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free