C++ - Find Median in a Stream (Running Median Problem)
Problem Statement
You are given a stream of integers.
You need to find the median after each insertion of a number into the stream.
Example 1
Input: [5, 15, 1, 3]
Output: [5, 10, 5, 4]
Explanation:
- After inserting **5**, median = **5**
- After inserting **15**, median = **(5+15)/2 = 10**
- After inserting **1**, median = **5**
- After inserting **3**, median = **(3+5)/2 = 4**
Efficient Approach: Using Two Heaps (Min-Heap & Max-Heap)
Max-Heap (left) → Stores the smaller half of numbers.
Min-Heap (right) → Stores the larger half of numbers.
Balancing condition:
If max-heap has more than 1 extra element than min-heap, move a top element to min-heap.
If the min-heap has more elements, move a top element to the max-heap.
Median Calculation:
If heaps are equal → Median is (max-heap top + min-heap top) / 2.
Else → Median is max-heap top (as max-heap will have one extra element).
Code Implementation
#include <iostream>
#include <queue>
using namespace std;
class MedianFinder {
private:
priority_queue<int> maxHeap; // Max-Heap (left half)
priority_queue<int, vector<int>, greater<int>> minHeap; // Min-Heap (right half)
public:
void addNum(int num) {
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
// Balance the heaps
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.top() + minHeap.top()) / 2.0;
}
return maxHeap.top();
}
};
int main() {
MedianFinder medianFinder;
int arr[] = {5, 15, 1, 3};
for (int num : arr) {
medianFinder.addNum(num);
cout << "Median after inserting " << num << ": " << medianFinder.findMedian() << endl;
}
return 0;
}
Explanation
Step-by-Step Execution for Input [5, 15, 1, 3]
Inserted Number Max-Heap (Left) Min-Heap (Right) Median
5 [5] [] 5
15 [5] [15] (5+15)/2 = 10
1 [1, 5] [15] 5
3 [3, 1] [5, 15] (3+5)/2 = 4
Time Complexity Analysis
Operation Complexity
Insertion O(log N) (heap insertion)
Finding Median O(1) (reading top element)
Overall Complexity O(N log N) for N elements
Alternative Approach: Using Multiset (Balanced BST)
Instead of heaps, we can use a Balanced BST (std::multiset) with iterators.
Code using std::multiset
#include <iostream>
#include <set>
using namespace std;
class MedianFinder {
private:
multiset<int> elements;
multiset<int>::iterator mid;
public:
MedianFinder() : mid(elements.end()) {}
void addNum(int num) {
elements.insert(num);
if (elements.size() == 1) {
mid = elements.begin();
} else if (num < *mid) {
if (elements.size() % 2 == 0) mid--;
} else {
if (elements.size() % 2 == 1) mid++;
}
}
double findMedian() {
int n = elements.size();
if (n % 2 == 0) {
return (*mid + *next(mid)) / 2.0;
}
return *mid;
}
};
int main() {
MedianFinder medianFinder;
int arr[] = {5, 15, 1, 3};
for (int num : arr) {
medianFinder.addNum(num);
cout << "Median after inserting " << num << ": " << medianFinder.findMedian() << endl;
}
return 0;
}
