These are the notes for DSA episode 44. Numbers arrive one at a time, and after every one you must say the median, the middle value. Last episode we met the heap; today we use two heaps at once: a max-heap for the smaller half and a min-heap for the bigger half, so the middle is always sitting on their tops. We start from a real-life problem (a food-delivery app showing the typical delivery time live), define the median and a data stream, solve it the obvious way (sort on every query), watch it hit Time Limit Exceeded on 2 lakh numbers, and finish with O(log n) per add and O(1) per median. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
A food-delivery app sees orders finish one by one, all day: 22 minutes, 30 minutes, 25 minutes… It shows customers the typical delivery time right now, updated after every order. Then one rider gets a flat tyre in the rain and an order takes 3 hours. The average jumps (22, 25, 30, 180 → 64.25 minutes) and scares everyone; the middle value, with half the orders faster and half slower, barely moves (27.5 minutes). That middle value is the median.
| In the delivery app | In code |
|---|---|
| Orders finishing one by one | a data stream of numbers |
| Recording one finished order | addNum(x) |
| Showing the typical time | findMedian() |
| The 3-hour order | an outlier |
Every word, from zero
- Mean (average): the sum of the values divided by how many there are.
- Median: sort the values and take the middle one. With an odd count it is the middle value; with an even count it is the average of the two middle values.
- Outlier: a value far away from the others; it moves the mean a lot and the median very little.
- Data stream: values arrive one at a time and keep coming; you never get the whole list up front.
- Min-heap / max-heap: from episode 43. A min-heap keeps its smallest item on top, a max-heap its largest.
peekO(1),offer/pollO(log n). PriorityQueue: Java's heap, a min-heap by default;new PriorityQueue<>(Collections.reverseOrder())makes a max-heap.Collections.reverseOrder(): a comparator that flips the natural order (bigger comes first).- Integer division: in Java
3 / 2is1(the fraction is dropped) when both sides areint;3 / 2.0is1.5.
Problem statement
Design a class MedianFinder with:
void addNum(int num): add the next number from the stream;double findMedian(): return the median of all numbers added so far.
| Calls | Result |
|---|---|
addNum(1), addNum(2), findMedian() |
1.5 |
addNum(3), findMedian() |
2.0 |
Constraints: up to 50,000 calls, values −10^5 … 10^5, findMedian only called when at least one number was added.
Brute force: keep everything, sort when asked
import java.util.*;
public class Main {
static class SlowMedian {
List<Integer> all = new ArrayList<>();
void addNum(int x) { all.add(x); }
double findMedian() {
Collections.sort(all);
int n = all.size();
if (n % 2 == 1) return all.get(n / 2);
return (all.get(n / 2 - 1) + all.get(n / 2)) / 2.0;
}
}
public static void main(String[] args) {
SlowMedian m = new SlowMedian();
m.addNum(1); m.addNum(2);
System.out.println(m.findMedian());
m.addNum(3);
System.out.println(m.findMedian());
}
}
Real output:
1.5
2.0
2 lakh orders: Time Limit Exceeded
Random rnd = new Random(44);
SlowMedian m = new SlowMedian();
long t0 = System.nanoTime();
double last = 0;
for (int j = 0; j < 200000; j++) {
m.addNum(rnd.nextInt(180) + 10);
last = m.findMedian();
}
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("median " + last + " min, " + ms + " ms");
Two lakh delivery times from 10 to 189 minutes, with a median after every order. In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s).
Why it is slow
- Every
findMediansorts the whole list. Even when the list is almost sorted (Java's TimSort is then close to linear), it still has to look at every element: at least O(n) per query. - 1 + 2 + 3 + … + 2 lakh ≈ 2 × 10^10 element visits: O(n²) over the whole stream, even in the best case (O(n² log n) in general).
- We only ever need the one or two values in the middle.
The key insight: two heaps
Picture students arriving one by one and splitting into two rooms by height. The shorter half is in the left room with its tallest at the door; the taller half is in the right room with its shortest at the door. The two students at the doors are exactly the middle of everyone.
low: a max-heap of the smaller half (top = the biggest of the small ones).high: a min-heap of the bigger half (top = the smallest of the big ones).- Rule 1: every number in
low≤ every number inhigh. - Rule 2: the sizes are equal, or
lowhas exactly one more. - Median:
low.peek()iflowis bigger (odd count), else(low.peek() + high.peek()) / 2.0.
Example: numbers 1, 3, 5, 7, 8, 9 → low = {5, 3, 1} (top 5), high = {7, 8, 9} (top 7) → median (5 + 7) / 2.0 = 6.0. Add 6: it belongs to the bigger half; then high has one more than low, so its top moves across. Now low has 4 items with top 6, and the median is 6.0 = low.peek().
addNum in three lines
low.offer(x); // 1: x joins the small half
high.offer(low.poll()); // 2: low's biggest moves right
if (high.size() > low.size()) low.offer(high.poll()); // 3: rebalance
Step 2 keeps rule 1 without any if: whatever x is, the largest of low ∪ {x} moves to high. Step 3 keeps rule 2. Three heap operations: O(log n).
Trace for 1, 2, 3:
| add | after step 1 | after step 2 | after step 3 | median |
|---|---|---|---|---|
| 1 | low {1} | low {}, high {1} | low {1}, high {} | 1.0 |
| 2 | low {2, 1} | low {1}, high {2} | (sizes equal) | (1 + 2) / 2.0 = 1.5 |
| 3 | low {3, 1} | low {1}, high {2, 3} | low {2, 1}, high {3} | 2.0 |
The optimal solution in Java
import java.util.*;
public class Main {
static class MedianFinder {
PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> high = new PriorityQueue<>();
void addNum(int x) {
low.offer(x);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
}
double findMedian() {
if (low.size() > high.size()) return low.peek();
return (low.peek() + high.peek()) / 2.0;
}
}
public static void main(String[] args) {
MedianFinder m = new MedianFinder();
m.addNum(1); m.addNum(2);
System.out.println(m.findMedian());
m.addNum(3);
System.out.println(m.findMedian());
MedianFinder d = new MedianFinder();
int[] xs = {-5, 40, 7, 7, 7, -100};
for (int x : xs) {
d.addNum(x);
System.out.print(d.findMedian() + " ");
}
System.out.println();
}
}
Real output:
1.5
2.0
-5.0 17.5 7.0 7.0 7.0 7.0
Negative numbers and duplicates work, and the outlier −100 does not move the median.
2 lakh orders in milliseconds
The same busy day with MedianFinder: real output median 100.0 min, 168 ms.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
class MedianFinder {
priority_queue<int> low; // max-heap: smaller half
priority_queue<int, vector<int>, greater<int>> high; // min-heap: bigger half
public:
void addNum(int x) {
low.push(x);
high.push(low.top()); low.pop();
if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
}
double findMedian() {
if (low.size() > high.size()) return low.top();
return ((long long)low.top() + high.top()) / 2.0;
}
};
int main() {
MedianFinder m;
m.addNum(1); m.addNum(2);
cout << fixed << setprecision(1) << m.findMedian() << "\n";
m.addNum(3);
cout << m.findMedian() << "\n";
MedianFinder d;
for (int x : {-5, 40, 7, 7, 7, -100}) { d.addNum(x); cout << d.findMedian() << " "; }
cout << "\n";
}
C++'s priority_queue is a max-heap by default (the opposite of Java); greater<int> makes the min-heap. Real output (g++ -O2 -std=c++17):
1.5
2.0
-5.0 17.5 7.0 7.0 7.0 7.0
The same solution in Python
import heapq
class MedianFinder:
def __init__(self):
self.low = [] # max-heap of the smaller half, stored as negatives
self.high = [] # min-heap of the bigger half
def add_num(self, x):
heapq.heappush(self.low, -x)
heapq.heappush(self.high, -heapq.heappop(self.low))
if len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def find_median(self):
if len(self.low) > len(self.high):
return float(-self.low[0])
return (-self.low[0] + self.high[0]) / 2
m = MedianFinder()
m.add_num(1); m.add_num(2)
print(m.find_median())
m.add_num(3)
print(m.find_median())
d = MedianFinder()
print(" ".join(str((d.add_num(x), d.find_median())[1]) for x in [-5, 40, 7, 7, 7, -100]))
heapq only has a min-heap, so the max-heap stores negated values. Python's / always gives a float. Real output:
1.5
2.0
-5.0 17.5 7.0 7.0 7.0 7.0
Three real bugs
Bug 1: integer division
return (low.peek() + high.peek()) / 2;
Real output on the LeetCode example: 1.0 then 2.0. 1 + 2 is an int, and 3 / 2 is 1; the .5 is thrown away before Java turns the result into a double. Divide by 2.0.
Bug 2: low without reverseOrder()
PriorityQueue<Integer> low = new PriorityQueue<>(); // a min-heap by mistake
// main: add 5, 1, 9
Real output: 1.0 instead of 5.0. low.poll() handed over its smallest number instead of its biggest, so the halves got mixed up, and low's top is now its smallest.
Bug 3: never rebalancing
void addNum(int x) {
if (low.isEmpty() || x <= low.peek()) low.offer(x);
else high.offer(x);
}
// main: add 5, 4, 3, 2, 1
Real output: 5.0 instead of 3.0. Every number was ≤ low's top, so all five went into low, and its top is not the middle. The sizes must stay equal or differ by one.
Complexity
| Approach | addNum | findMedian | Whole stream of n | Space | 2 lakh orders |
|---|---|---|---|---|---|
| Sort on every query | O(1) | O(n log n) (≥ O(n)) | O(n²) or worse | O(n) | TLE |
| Max-heap + min-heap | O(log n) | O(1) | O(n log n) | O(n) | 0.17 s |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
/ 2 instead of / 2.0 |
1.0 instead of 1.5 |
integer division | divide by 2.0 |
low = new PriorityQueue<>() |
1.0 instead of 5.0 |
low must give its biggest |
Collections.reverseOrder() |
| No rebalancing | 5.0 instead of 3.0 |
one half grows too big | move a top across when sizes differ by 2 |
Sorting on every findMedian |
Time Limit Exceeded | O(n²) over the stream | two heaps |
Values near Integer.MAX_VALUE |
a negative "median" | low.peek() + high.peek() overflows |
((long) a + b) / 2.0 |
Calling findMedian on an empty finder |
NullPointerException (unboxing a null from peek()) |
no numbers yet | check low.isEmpty() first |
Mini project: the live delivery board
Simulate a day of 1,000 orders with mostly 15–45 minute deliveries and a few 2–3 hour outliers. After every order print the mean and the median side by side, and mark the moments when the mean jumps by more than 5 minutes while the median stays within 1 minute. Then add the 90th percentile (practice 2) as "most orders arrive within … minutes".
Practice
- Values only between 0 and 100: find the median without heaps.
Solution
Keep a counting array of 101 slots. addNum is O(1); findMedian walks at most 101 slots, which is O(1) for a fixed range.
static class SmallMedian {
int[] c = new int[101];
int n = 0;
void addNum(int x) { c[x]++; n++; }
double findMedian() {
int a = kth((n - 1) / 2), b = kth(n / 2);
return (a + b) / 2.0;
}
int kth(int k) { // the k-th smallest, 0-based
for (int v = 0; v <= 100; v++) {
if (k < c[v]) return v;
k -= c[v];
}
return -1;
}
}
Adding 22, 30, 25, 100 → 27.5. Real output. (For an odd count both kth calls return the same middle value.)
- Track the 90th percentile instead of the median.
Solution
The same two heaps, but low keeps ⌈0.9 · n⌉ numbers instead of half; its top is the 90th percentile (nearest-rank).
static class P90 {
PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> high = new PriorityQueue<>();
void add(int x) {
low.offer(x);
high.offer(low.poll());
int n = low.size() + high.size();
int want = (int) Math.ceil(0.9 * n);
while (low.size() < want) low.offer(high.poll());
}
int get() { return low.peek(); }
}
Adding 1, 2, …, 20 → 18. Real output.
- Sliding window median (LeetCode 480): the median of every window of k consecutive numbers.
Solution
Add the new number as before; when a number leaves the window, remove it from whichever heap holds it (PriorityQueue.remove(Object) is O(k)) and rebalance.
static double[] windowMedian(int[] nums, int k) {
PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> high = new PriorityQueue<>();
double[] ans = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
low.offer(nums[i]);
high.offer(low.poll());
if (high.size() > low.size()) low.offer(high.poll());
if (i >= k) {
int out = nums[i - k];
if (out <= low.peek()) low.remove(out); else high.remove(out);
while (low.size() < high.size()) low.offer(high.poll());
while (low.size() > high.size() + 1) high.offer(low.poll());
}
if (i >= k - 1)
ans[i - k + 1] = k % 2 == 1 ? low.peek() : ((long) low.peek() + high.peek()) / 2.0;
}
return ans;
}
windowMedian({1, 3, -1, -3, 5, 3, 6, 7}, 3) → [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]. Real output. This is O(n · k); a TreeMap or lazy deletion makes it O(n log k).
Quick quiz
low (max-heap) holds 2, 4, 6; high (min-heap) holds 8, 10. What does findMedian() return: 6.0, 7.0, 8.0 or 5.0?
Answer
6.0. low has one more number, so the count (5) is odd and the median is low's top: its biggest, 6.
Interview questions
- Why a max-heap for the smaller half? We need the biggest of the small numbers instantly; a max-heap keeps it on top.
- Why is
findMedianO(1)? It only peeks at one or two tops. - Why does the three-line
addNumkeep everylow≤ everyhigh? Step 2 always moves the largest oflow ∪ {x}intohigh. - What if most numbers are in a small range? A counting array (practice 1) makes both operations O(1) for a fixed range.
- What if numbers must also be removed? Sliding window median: remove from the right heap and rebalance (practice 3), or use lazy deletion / a balanced tree.
- Can the sum of the two tops overflow? Yes for values near the
intlimit; add them aslong. - Mean vs median? The mean is O(1) to keep (a running sum and a count) but is pulled by outliers; the median needs the two heaps but is robust.
Glossary
| Term | Meaning |
|---|---|
| Mean (average) | The sum of the values divided by their count |
| Median | The middle value after sorting; the average of the two middle values for an even count |
| Outlier | A value far away from the others |
| Data stream | Values arriving one at a time, with no full list up front |
addNum / findMedian |
Add the next number / return the current median |
| Min-heap / max-heap | A heap with the smallest / largest item on top |
PriorityQueue |
Java's heap; a min-heap by default |
Collections.reverseOrder() |
A comparator that flips the order; makes a max-heap |
low / high |
The max-heap of the smaller half / the min-heap of the bigger half |
| Rebalance | Moving a top from one heap to the other to keep the sizes equal (or low one more) |
| Integer division | int / int in Java drops the fraction: 3 / 2 == 1 |
| Percentile | The value below which a given percentage of the data falls |
| Overflow | A result too big for its type wraps around to a wrong (often negative) value |
| O(log n), O(1) | The cost of one heap operation / of one peek |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
Summary
- The median is the middle value (or the average of the two middle values); an outlier moves the mean, not the median.
- Sorting on every query is O(n²) over a stream: TLE on 2 lakh numbers.
- Two heaps:
low= max-heap of the smaller half (Collections.reverseOrder()),high= min-heap of the bigger half; everylow≤ everyhigh, sizes equal orlowone more. addNum: offer tolow, movelow's top tohigh, movehigh's top back ifhighgot bigger: O(log n).findMedian: one or two peeks, divide by2.0: O(1).
Next episode: Tries: implement a trie, then Word Search II (hard).