Find Median from Stream 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

Design a data structure that supports addNum(num) and findMedian() efficiently for a stream of numbers.

mf = MedianFinder()
mf.addNum(1)    # [1]
mf.addNum(2)    # [1, 2]
mf.findMedian() # → 1.5
mf.addNum(3)    # [1, 2, 3]
mf.findMedian() # → 2.0

The two-heap trick — one of the most elegant data structure designs:

Max-heap (small): Stores the smaller half of numbers
Min-heap (large): Stores the larger half of numbers
All values in max-heap ≤ All values in min-heap
Keep heaps balanced (size difference ≤ 1)
Median = top of larger heap, or average of both tops

# After adding [1, 2, 3, 4, 5]:
# max_heap (small half): [3, 1, 2]  → top = 3
# min_heap (large half): [4, 5]     → top = 4
# Median = 3 (max_heap has 1 more element)

addNum: O(log n), findMedian: O(1). This is a FAANG favorite!

📋 Instructions

Implement MedianFinder with addNum and findMedian. Test with the provided sequence.

Two heaps: small (max-heap via negation) and large (min-heap). addNum: push to small, then move top of small to large. If large is bigger, move top of large back to small. findMedian: if same size, average both tops. Otherwise, top of small.

🧪 Test Cases

Input

mf.findMedian()

Expected

1.5

Test case 1

Input

mf.findMedian()

Expected

2.0

Test case 2

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›