.png)
Find the Median in a Stream of Integers
Problem Statement
You are given a stream of integers (numbers arrive one by one).
After inserting each number, you need to output the median of all numbers seen so far.
Definition of Median
- If the count is odd → middle element
- If the count is even → average of two middle elements
Example
Input Stream
5, 15, 1, 3
Output
5
10
5
4
Explanation
| Numbers Seen | Sorted | Median |
|---|---|---|
| [5] | [5] | 5 |
| [5,15] | [5,15] | (5+15)/2 = 10 |
| [5,15,1] | [1,5,15] | 5 |
| [5,15,1,3] | [1,3,5,15] | (3+5)/2 = 4 |
Why This Problem Is Important
- Very common FAANG interview problem
- Tests:
- Data structures
- Heap usage
- Real-time computation
- Core concept for:
- Streaming algorithms
- Online statistics
- Priority queues
Approaches Overview
| Approach | Technique | Time (Insert) | Space |
|---|---|---|---|
| Approach 1 | Sort Every Time | O(n log n) | O(n) |
| Approach 2 | Insertion in Sorted List | O(n) | O(n) |
| Approach 3 | Two Heaps (Optimal) | O(log n) | O(n) |
Approach 1: Sort After Each Insertion (Brute Force)
Idea
- Store all numbers
- Sort after every insertion
- Compute median
Time & Space
- Time: O(n log n) per insertion
- Space: O(n)
Python
arr = []
def add(num):
arr.append(num)
arr.sort()
n = len(arr)
if n % 2 == 1:
return arr[n//2]
return (arr[n//2 - 1] + arr[n//2]) // 2
for x in [5,15,1,3]:
print(add(x))
C++
#include
using namespace std;
int main() {
vector arr;
int stream[] = {5,15,1,3};
for(int x : stream) {
arr.push_back(x);
sort(arr.begin(), arr.end());
int n = arr.size();
if(n % 2)
cout << arr[n/2] << endl;
else
cout << (arr[n/2-1] + arr[n/2]) / 2 << endl;
}
}
Java
import java.util.*;
class MedianStream {
public static void main(String[] args) {
ArrayList arr = new ArrayList<>();
int[] stream = {5,15,1,3};
for(int x : stream) {
arr.add(x);
Collections.sort(arr);
int n = arr.size();
if(n % 2 == 1)
System.out.println(arr.get(n/2));
else
System.out.println((arr.get(n/2-1) + arr.get(n/2)) / 2);
}
}
}
JavaScript
let arr = [];
let stream = [5,15,1,3];
for(let x of stream){
arr.push(x);
arr.sort((a,b)=>a-b);
let n = arr.length;
if(n % 2)
console.log(arr[Math.floor(n/2)]);
else
console.log((arr[n/2-1] + arr[n/2]) / 2);
}
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
List arr = new List();
int[] stream = {5,15,1,3};
foreach(int x in stream) {
arr.Add(x);
arr.Sort();
int n = arr.Count;
if(n % 2 == 1)
Console.WriteLine(arr[n/2]);
else
Console.WriteLine((arr[n/2-1] + arr[n/2]) / 2);
}
}
}
Output
5
10
5
4
Approach 2: Maintain Sorted Order (Insertion)
Idea
- Insert element at correct position
- No full sorting
- Median from middle
Time & Space
- Time: O(n) per insertion
- Space: O(n)
Python
import bisect
arr = []
def add(num):
bisect.insort(arr, num)
n = len(arr)
if n % 2:
return arr[n//2]
return (arr[n//2 - 1] + arr[n//2]) // 2
for x in [5,15,1,3]:
print(add(x))
C++
#include
using namespace std;
int main() {
vector arr;
int stream[] = {5,15,1,3};
for(int x : stream) {
arr.insert(lower_bound(arr.begin(), arr.end(), x), x);
int n = arr.size();
if(n % 2)
cout << arr[n/2] << endl;
else
cout << (arr[n/2-1] + arr[n/2]) / 2 << endl;
}
}
Java
import java.util.*;
class MedianStream {
static ArrayList arr = new ArrayList<>();
static void add(int x) {
int i = Collections.binarySearch(arr, x);
if(i < 0) i = -i - 1;
arr.add(i, x);
int n = arr.size();
if(n % 2 == 1)
System.out.println(arr.get(n/2));
else
System.out.println((arr.get(n/2-1) + arr.get(n/2)) / 2);
}
public static void main(String[] args) {
int[] stream = {5,15,1,3};
for(int x : stream)
add(x);
}
}
JavaScript
let arr = [];
function insert(num){
let i = 0;
while(i < arr.length && arr[i] < num) i++;
arr.splice(i, 0, num);
let n = arr.length;
if(n % 2)
return arr[Math.floor(n/2)];
return Math.floor((arr[n/2-1] + arr[n/2]) / 2);
}
[5,15,1,3].forEach(x => console.log(insert(x)));
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
List arr = new List();
int[] stream = {5,15,1,3};
foreach(int x in stream) {
int i = arr.BinarySearch(x);
if(i < 0) i = ~i;
arr.Insert(i, x);
int n = arr.Count;
if(n % 2 == 1)
Console.WriteLine(arr[n/2]);
else
Console.WriteLine((arr[n/2-1] + arr[n/2]) / 2);
}
}
}
Output
5
10
5
4
Approach 3: Two Heaps (Optimal)
Idea
- Max Heap: stores lower half
- Min Heap: stores upper half
- Balance both heaps
- Median from tops
Rules
- Size difference ≤ 1
- MaxHeap top ≤ MinHeap top
Time & Space
- Time: O(log n) per insertion
- Space: O(n)
Python
import heapq
low = []
high = []
def add(num):
heapq.heappush(low, -num)
heapq.heappush(high, -heapq.heappop(low))
if len(high) > len(low):
heapq.heappush(low, -heapq.heappop(high))
if len(low) > len(high):
return -low[0]
return (-low[0] + high[0]) // 2
for x in [5,15,1,3]:
print(add(x))
C++
#include
using namespace std;
int main() {
priority_queue low;
priority_queue, greater> high;
int stream[] = {5,15,1,3};
for(int x : stream) {
low.push(x);
high.push(low.top());
low.pop();
if(high.size() > low.size()) {
low.push(high.top());
high.pop();
}
if(low.size() > high.size())
cout << low.top() << endl;
else
cout << (low.top() + high.top()) / 2 << endl;
}
}
Java
import java.util.*;
class MedianStream {
public static void main(String[] args) {
PriorityQueue low =
new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue high = new PriorityQueue<>();
int[] stream = {5,15,1,3};
for(int x : stream) {
low.add(x);
high.add(low.poll());
if(high.size() > low.size())
low.add(high.poll());
if(low.size() > high.size())
System.out.println(low.peek());
else
System.out.println((low.peek() + high.peek()) / 2);
}
}
}
JavaScript (Conceptual)
let arr = [];
function add(num){
arr.push(num);
arr.sort((a,b)=>a-b);
let n = arr.length;
if(n % 2)
return arr[Math.floor(n/2)];
return Math.floor((arr[n/2-1] + arr[n/2]) / 2);
}
[5,15,1,3].forEach(x => console.log(add(x)));
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
List arr = new List();
int[] stream = {5,15,1,3};
foreach(int x in stream) {
arr.Add(x);
arr.Sort();
int n = arr.Count;
if(n % 2 == 1)
Console.WriteLine(arr[n/2]);
else
Console.WriteLine((arr[n/2-1] + arr[n/2]) / 2);
}
}
}
Output
5
10
5
4
Final Summary
- Sorting: Easy, slow
- Insertion: Better, still O(n)
- Two Heaps: INTERVIEW STANDARD
- Handles:
- Real-time data
- Large streams
- Core heap problem
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
