Find Median from Data Stream
A hard Heap interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Heap
- Sheets
- 2
- Core for
- 10 roles
The problem
Numbers arrive one by one. Build a structure with two operations: add a number, and report the median of everything added so far. With an odd count the median is the middle value; with an even count it is the average of the two middle values.
Example 1
- Input
- addNum(1), addNum(2), findMedian() -> 1.5, addNum(3), findMedian() -> 2
- Output
- [null, null, 1.5, null, 2]
- Why
- After adding 1 and 2, the sorted list is [1,2] and median is (1+2)/2 = 1.5. After adding 3, the sorted list is [1,2,3] and median is 2.
Example 2
- Input
- addNum(1), findMedian() -> 1, addNum(2), findMedian() -> 1.5
- Output
- [null, 1, null, 1.5]
- Why
- After adding just 1, the median is 1. After adding 2, sorted list is [1,2], median is 1.5.
Constraints
- -10^5 <= num <= 10^5
- At most 5 * 10^4 calls will be made to addNum and findMedian
How to think about it
Updated 2026-09-29The median divides numbers into two halves: smaller numbers and larger numbers. You never care about the internal order within either half, only the boundary where they touch. Putting the lower half into a max-heap and the upper half into a min-heap places both middle candidates directly at the roots.
Approaches, worst first
Insertion sort into dynamic array
time O(n) · space O(n)
Maintain a sorted array. Use binary search to locate the correct insertion index for the incoming number, then insert it. Finding the median takes O(1), but shifting elements on insertion burns linear time on every add, so the add dominates.
Two balancing heapsWrite this one
time O(log n) · space O(n)
Use a max-heap for the lower half and a min-heap for the upper half. Route the incoming value through the heaps and rebalance sizes so their lengths differ by at most one. The median is either the top of the larger heap or the average of both tops, so the add dominates and finding the median is free.
Where people lose marks · 3
- Returning integer division when averaging the two middle numbers for an even total count. 1 and 2 must produce 1.5, so floating-point division is mandatory.
- Letting the two heaps invert their order. Never insert directly into one heap without checking whether the new value actually belongs on the other side of the median boundary.
- Allowing heap sizes to drift apart by more than one element. Balancing must happen on every single addNum call, not deferred until findMedian.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
More Heap problems
Target Roles
Core requirement for 10 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .