Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Hard

Find Median from Data Stream

Find Median from Data Stream with two heaps: a max-heap for the lower half and a min-heap for the upper half, O(log n) add, O(1) median. Tested Python, visual.

Also searched as: running median using two heaps · median of a stream · two heaps pattern

🔺

Try it live Free

Binary Heap & Priority Queue

Practise push and pop-min in the heap lab and notice that only the root is cheap to read; this design uses two heaps so the two middle values are always sitting at the roots.

Open the playground →

The problem

Design a class that accepts numbers one at a time with add_num(x) and can report the median of everything added so far with find_median(). For an even count, the median is the average of the two middle values.

Inputadd_num(1), add_num(2), find_median(), add_num(3), find_median()
Output1.5, then 2

The key insight

Split the numbers into a lower half and an upper half. Keep the lower half in a max-heap (its root is the largest small number) and the upper half in a min-heap (its root is the smallest big number). If the halves stay balanced in size, the median is one root or the average of both roots.

Brute force first: Keeping a sorted list with bisect.insort gives an O(1) median but O(n) insertion, because elements must shift.

Step-by-step approach

  1. Keep low as a max-heap (store negatives) and high as a min-heap.
  2. To add x, push it onto low, then move the largest of low into high; this guarantees every value in low is at most every value in high.
  3. If high now has more elements than low, move its smallest back to low.
  4. So low always has the same number of elements as high, or one more.
  5. Median: if low is bigger, return its root; otherwise return the average of both roots.

Python solution

PYTHON 3tested
import heapq


class MedianFinder:
    def __init__(self):
        self.low = []       # max-heap (negated): smaller half
        self.high = []      # min-heap: larger half

    def add_num(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))   # keep order
        if len(self.high) > len(self.low):                     # keep sizes
            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

Complexity

TimeO(log n) add, O(1) median
SpaceO(n)

Each add does a constant number of heap pushes and pops, O(log n) each. Reading the median only looks at the two roots.

Common mistakes

Frequently asked questions

What is the time and space complexity of the two-heap median?

add_num is O(log n), find_median is O(1), and the two heaps together store all n numbers, O(n) space.

Why a max-heap for the lower half?

You need the largest of the small numbers at a glance, and a max-heap keeps it at the root. Symmetrically, the min-heap keeps the smallest of the large numbers at its root.

What if all numbers are in a small range, like 0 to 100?

Keep a count array of size 101 and walk it to find the middle, which is O(100) per query and O(1) per add.

How do I handle a sliding window median?

Use the same two heaps with lazy deletion (mark removed values and discard them when they reach a root), or a sorted container that supports removal.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.