SyntaxPilot
Courses/DSA and Coding Problems/Lesson 44
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 44 of 90

Median from a data stream with two heaps (hard)

queued

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. peek O(1), offer / poll O(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 / 2 is 1 (the fraction is dropped) when both sides are int; 3 / 2.0 is 1.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 findMedian sorts 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 in high.
  • Rule 2: the sizes are equal, or low has exactly one more.
  • Median: low.peek() if low is 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

  1. 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.)

  1. 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.

  1. 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

  1. Why a max-heap for the smaller half? We need the biggest of the small numbers instantly; a max-heap keeps it on top.
  2. Why is findMedian O(1)? It only peeks at one or two tops.
  3. Why does the three-line addNum keep every low ≤ every high? Step 2 always moves the largest of low ∪ {x} into high.
  4. What if most numbers are in a small range? A counting array (practice 1) makes both operations O(1) for a fixed range.
  5. 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.
  6. Can the sum of the two tops overflow? Yes for values near the int limit; add them as long.
  7. 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; every low ≤ every high, sizes equal or low one more.
  • addNum: offer to low, move low's top to high, move high's top back if high got bigger: O(log n). findMedian: one or two peeks, divide by 2.0: O(1).

Next episode: Tries: implement a trie, then Word Search II (hard).