Log inSign up
hardLeetCodeNot Started

Find Median from Data Stream

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class: - MedianFinder(): Initializes the object. - void addNum(int num): Adds the integer num from the data stream. - double findMedian(): Returns the median of all elements so far in O(1) time.

Example 1 · Example 1: Sequence of Additions:

Input: addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Output: [null, null, 1.5, null, 2.0]
Explanation: 1. addNum(1): small=[1], large=[] -> median = 1 2. addNum(2): small=[1], large=[2] -> median = (1 + 2)/2 = 1.5 3. addNum(3): small=[1, 2], large=[3] -> median = 2.0 Two-Heaps Structure: [Max-Heap: Lower] [Min-Heap: Upper] (2) (3) / (1)

Constraints:

  • -105 <= num <= 105
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 104 calls will be made to addNum and findMedian.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Two-Heaps design pattern for continuous median tracking.
  • Maintain size balance and order invariants across two priority queues.
  • Implement the class cleanly in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Continuous stream of data with frequent median queries.
  • Need logarithmic insertion and O(1) median retrieval.
  • Classic Two-Heaps pattern.

Algorithmic Decision Tree:

  • Sorting upon every median query takes O(N log N) which times out.
  • Maintaining a sorted array takes O(N) shift time per insertion.
  • Two Heaps provide O(log N) insert and instant O(1) median lookup.

Connected Patterns:

Sliding Window MedianKth Largest Element in a Stream

1. Brute Force — Append & Sort

Intuition

Store all elements in a list. When findMedian() is requested, sort the list in O(N log N) and return the middle element or average of the two middle elements.

When to apply: When total numbers N <= 500 and queries are rare.

Algorithm

  1. Step 1: addNum(num): push num to list.
  2. Step 2: findMedian(): sort list ascending.
  3. Step 3: If list length is odd, return list[n / 2].
  4. Step 4: If list length is even, return (list[n / 2 - 1] + list[n / 2]) / 2.0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class MedianFinder {
7 vector<int> nums;
8public:
9 MedianFinder() {}
10
11 void addNum(int num) {
12 nums.push_back(num);
13 }
14
15 double findMedian() {
16 vector<int> sortedNums = nums;
17 sort(sortedNums.begin(), sortedNums.end());
18 int n = sortedNums.size();
19 if (n % 2 == 1) {
20 return sortedNums[n / 2];
21 }
22 return (sortedNums[n / 2 - 1] + sortedNums[n / 2]) / 2.0;
23 }
24};
25
26int main() {
27 MedianFinder mf;
28 mf.addNum(1);
29 mf.addNum(2);
30 cout << "Median: " << mf.findMedian() << endl; // 1.5
31 mf.addNum(3);
32 cout << "Median: " << mf.findMedian() << endl; // 2.0
33 return 0;
34}

Time & Space Complexity

  • Time complexity: addNum: O(1), findMedian: O(N log N) — O(N log N) per median query.
  • Space complexity: O(N) — O(N) storage.

Why Brute Force Doesn't Scale:

50,000 insertions into an array take ~1.25 * 109 operations (several seconds). Two-Heaps execute 50,000 insertions in ~8 * 105 operations (15ms).

Two Heaps process 50,000 stream elements in under 20ms.

2. Better — Insertion Sort via Binary Search

Intuition

Use binary search (lower_bound) to find where num belongs, then insert it. Finding median is instant O(1) indexed access.

When to apply: When read queries dominate and write queries are fewer.

Algorithm

  1. Step 1: addNum(num): use binary search to locate insertion index in O(log N).
  2. Step 2: Insert num at index (shifts elements taking O(N)).
  3. Step 3: findMedian(): directly index array in O(1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class MedianFinder {
7 vector<int> nums;
8public:
9 MedianFinder() {}
10
11 void addNum(int num) {
12 auto it = lower_bound(nums.begin(), nums.end(), num);
13 nums.insert(it, num);
14 }
15
16 double findMedian() {
17 int n = nums.size();
18 if (n % 2 == 1) return nums[n / 2];
19 return (nums[n / 2 - 1] + nums[n / 2]) / 2.0;
20 }
21};
22
23int main() {
24 MedianFinder mf;
25 mf.addNum(1);
26 mf.addNum(2);
27 cout << "Median: " << mf.findMedian() << endl;
28 mf.addNum(3);
29 cout << "Median: " << mf.findMedian() << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: addNum: O(N), findMedian: O(1) — O(N) per addition due to array shifting.
  • Space complexity: O(N) — O(N) storage.

3. Optimal — Two Heaps (Max-Heap & Min-Heap)

Intuition

Push to small (Max-Heap), pop max and push to large (Min-Heap). If large size exceeds small size, balance by popping large and pushing to small. small either has equal elements or exactly 1 more element than large.

When to apply: Standard optimal design pattern for continuous median streams.

Algorithm

  1. Step 1: Push num to small (Max-Heap).
  2. Step 2: Move small.top() to large (Min-Heap) to maintain order invariant.
  3. Step 3: If large.size() > small.size(), move large.top() back to small.
  4. Step 4: findMedian(): if small.size() > large.size(), return small.top(). Else return (small.top() + large.top()) / 2.0.

Interactive Trace for Find Median from Data Stream

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: addNum(1)
Visual state
Values and pointers at this exact step
tree
MaxHeap Root: 1
1

Node order shown; add connections to display explicit tree edges.

median: s1
Check / comparison
Size is odd (1). Median = small.top() = 1.0.
Decision / next transition
Invariants hold.
Why this step matters

Step 1: addNum(1). Inserted into small (Max-Heap). small=[1], large=[].

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <queue>
3using namespace std;
4
5class MedianFinder {
6 priority_queue<int> small; // Max-Heap for lower half
7 priority_queue<int, vector<int>, greater<int>> large; // Min-Heap for upper half
8
9public:
10 MedianFinder() {}
11
12 void addNum(int num) {
13 small.push(num);
14 large.push(small.top());
15 small.pop();
16
17 if (large.size() > small.size()) {
18 small.push(large.top());
19 large.pop();
20 }
21 }
22
23 double findMedian() {
24 if (small.size() > large.size()) {
25 return small.top();
26 }
27 return (small.top() + large.top()) / 2.0;
28 }
29};
30
31int main() {
32 MedianFinder mf;
33 mf.addNum(1);
34 mf.addNum(2);
35 cout << "Median: " << mf.findMedian() << endl; // 1.5
36 mf.addNum(3);
37 cout << "Median: " << mf.findMedian() << endl; // 2.0
38 return 0;
39}

Time & Space Complexity

  • Time complexity: addNum: O(log N), findMedian: O(1) — O(log N) insertion, O(1) median query.
  • Space complexity: O(N) — O(N) heap storage across the two priority queues.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Append & Sort on QueryaddNum: O(1), findMedian: O(N log N)O(N)Append num to vector. When findMedian is called, sort vector and pick middle element(s).Sorting upon every query.
2.Better — Insertion Sort (Binary Search Insert)addNum: O(N), findMedian: O(1)O(N)Maintain a sorted array by using binary search to find insertion point and shift elements.Linear shifting on array insert.
3.Optimal — Two Heaps (Max-Heap & Min-Heap)OptimaladdNum: O(log N), findMedian: O(1)O(N)Balance lower half in Max-Heap and upper half in Min-Heap. Invariants maintain roots as median candidates.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Returning integer division

In languages like C++/Java, must divide by 2.0 to avoid truncating 1.5 to 1.

Letting sizes drift by > 1

Violates median invariant.

Allowing small.top() > large.top()

The routing step (push to small, transfer to large, re-balance) guarantees this invariant.

Crucial Edge Cases to Validate:

  • Single element stream — Correctly returns that single element as a double.
  • Even number of elements — Averages the roots of small and large.
  • All identical elements — Correctly partitions evenly between small and large.
  • Negative numbers — Negative numbers balance correctly without edge-case distortion.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the two-heap diagram with small (Max-Heap) on the left and large (Min-Heap) on the right.
  2. Emphasize the clean 3-line balancing idiom: push to small, transfer small.top to large, and transfer large.top back if sizes skew.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the two-heap design require small (Max-Heap) to hold the lower half of numbers?

Back to DSA Sheet