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
- Declare
lowas aPriorityQueue<Integer>with the comparator(x, y) -> y - x. Java'sPriorityQueueis a min-heap, and this comparator reverses the order, so the largest value comes out first. - Declare
highas a plainPriorityQueue<Integer>, a min-heap. - In
addNum, addnumtolowfirst. Every new number goes through the lower half. - Move the top of
lowtohighwithhigh.add(low.poll()).poll()removes and returns the largest value oflow. Whatevernumwas, this moves the largest of the lower half upward, which keeps every value inhighat least every value inlow. Ifnumwas small, it stays inlowand a larger value moves up instead. - Rebalance. If
highis now bigger thanlow, move the top ofhighback tolow. After this, the sizes are equal orlowis one larger. - In
findMedian, handle an odd count. Iflowis larger, returnlow.peek(), which reads the top without removing it. TheIntegerbecomes adoubleautomatically. - 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:
PriorityQueuelives injava.util. In a file of your own, addimport java.util.PriorityQueue;orimport java.util.*;.- Integer division.
3 / 2is 1 in Java, while3 / 2.0is 1.5. Dividing the sum by2.0keeps the half. - The comparator
(x, y) -> y - xcan overflow for values far apart:Integer.MIN_VALUE - 1wraps to 2147483647. Here the numbers stay between -100,000 and 100,000, so it is safe. For arbitraryintvalues, useCollections.reverseOrder()or(x, y) -> Integer.compare(y, x). - The sum of the two tops can't overflow here.
low.peek() + high.peek()adds twoIntegers asints before the division, which is fine for this lesson's range. With values nearInteger.MAX_VALUEit would wrap, and the fix is to add asdoubleorlong. peek()returnsnullon an empty heap, and unboxing thatnullthrows aNullPointerException. The lesson only callsfindMedianafter at least oneaddNum.
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),lowhas one value andhighnone, sofindMedian()returns 5.0. - Duplicates. Both -3s count: after 5, -3, -3 the median is -3.0.
- Asking twice.
findMedianonly reads the tops, so repeated calls give the same answer. With 4 and 3 added, it returns 3.5 both times. - Dividing by
2instead of2.0. The sum of two ints divided by the int2truncates, so a median of 2.5 would come out as 2. - Wrong heap direction. A default
PriorityQueueforlowwould 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, then2.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.
