# Find Median in a Stream

## Problem Statement

Given are some integers, which are read from the data stream. The task is to find the median of the integers read so far.

The median is the middle value of a sorted list of integers. If the size of the list is even, the median is the average of the two middle elements.

Examples:
Input: [1, 2, 3,…]
Output: [1, 1.5, 2..]
Explanation:

• The list contains [1]. So, median = 1 / 1 = 1
• The list contains [1, 2]. Median = (1 + 2) / 2 = 1.5
• The list contains [1, 2, 3]. Median = (1 + 2 + 3) / 3 = 2

## Approach 1: Sorting

The most basic approach is to store the integers in a list and sort the list every time for calculating the median.

Algorithm:

• Initialize a list for storing the integers.
• Sort the list every time.
• Print the median.

### C++ Code

```class MedianFinder {
vector < int > store;

public:
store.push_back(num);
}
double findMedian() {
sort(store.begin(), store.end());

int n = store.size();
return (n & 1 ? store[n / 2] : ((double) store[n / 2 - 1] + store[n / 2]) * 0.5);
}
};```

### Java Code

``` class MedianFinder {
List < Integer > input = new ArrayList < > ();

}

public double findMedian() {
Collections.sort(input);
int len = input.size();
if (len % 2 == 1) return input.get(len / 2);
return 0.5 * (input.get(len / 2) + input.get(len / 2 - 1));
}
}```

### Python Code

```class MedianFinder:
def __init__(self):
self.array = []

def addNum(self, num: int) -> None:
self.array.append(num)

def findMedian(self) -> float:
self.array.sort()
n = len(self.array)
if not self.array or n == 1:
return 0 or self.array[0]
elif n & 1:
return self.array[n // 2]
else:
return (self.array[n // 2] + self.array[(n // 2) - 1]) / 2```

Time Complexity:O(NlogN), where N is a number of elements.
Space Complexity:O(N), for storing list.

## Approach 2: Insertion Sort

In the previous approach, we sorted the list every time. Instead of sorting, we can insert the item in their specific position to keep the list always sorted.

Algorithm:

• We assume the list is already sorted.
• When a new integer comes up, apply binary search to insert the integer in its correct position.
• Now, the list is sorted and you can find the median.

### C++ Implementation

```class MedianFinder {
vector < int > store;

public:
if (store.empty())
store.push_back(num);
else
store.insert(lower_bound(store.begin(), store.end(), num), num);
}
double findMedian() {
int n = store.size();
return n & 1 ? store[n / 2] : ((double) store[n / 2 - 1] + store[n / 2]) * 0.5;
}
};```

### Java Implementation

``` class MedianFinder {
List < Integer > data;
public MedianFinder() {
data = new ArrayList();
}

int idx = Collections.binarySearch(data, num);
if (idx >= 0) {
} else {
}
}

public double findMedian() {
int len = data.size();
int mid = data.get(len / 2);
if (len % 2 == 1) {
return mid;
} else {
return 1.0 * ((data.get(len / 2 - 1)) + mid) / 2;
}
}
}```

### Python Implementation

```class MedianFinder:
def __init__(self):
self.q = []

bisect.insort(self.q, num)

def findMedian(self):
n = len(self.q)
m = n >> 1
return self.q[m] if n & 1 else (self.q[m - 1] + self.q[m]) / 2```

Time Complexity: O(N), where N is a number of elements.
Space Complexity: O(N), for storing list.

## Approach 3: Two Heaps

The idea is to use a max heap and a min-heap. Max heap is used to store the smaller half of the number and the min-heap is used to store the larger half of the numbers.

Algorithm

• If the current element to be added is less than the maximum element of the max heap, then add this to the max heap.
• If the difference between the size of the max and min heap becomes greater than 1, the top element of the max heap is removed and added to the min-heap.
• If the current element to be added is greater than the maximum element of the min-heap, then add this to the min-heap.
• If the difference between the size of the max and min heap becomes greater than 1, the top element of the min-heap is removed and added to the max heap.

### C++ Code For Two Heaps

```void findMedian(int arr[], int n) {
priority_queue < int > lowerHalf;
priority_queue < int, vector < int > , greater < int >> higherHalf;

int median;
for (int size = 1; size <= n; size++) {
if (!lowerHalf.empty() && lowerHalf.top() > arr[size - 1]) {
lowerHalf.push(arr[size - 1]);

if (lowerHalf.size() > higherHalf.size() + 1) {
higherHalf.push(lowerHalf.top());
lowerHalf.pop();
}
} else {
higherHalf.push(arr[size - 1]);

if (higherHalf.size() > lowerHalf.size() + 1) {
lowerHalf.push(higherHalf.top());
higherHalf.pop();
}
}
if (size % 2 == 1) {
if (higherHalf.size() > lowerHalf.size()) {
median = higherHalf.top();
} else {
median = lowerHalf.top();
}
} else {
median = (lowerHalf.top() + higherHalf.top()) / 2;
}
cout << median << " ";
}
}```

### Java Code For Two Heaps

```public class Solution {

public static void findMedian(int arr[]) {
int n = arr.length;

PriorityQueue < Integer > lowerHalf = new PriorityQueue < > (new Comparator < Integer > () {
@Override
public int compare(Integer first, Integer second) {
return (second - first);
}
});

PriorityQueue < Integer > higherHalf = new PriorityQueue < > ();

int median;
for (int size = 1; size <= n; size++) {
if (!lowerHalf.isEmpty() && lowerHalf.peek() > arr[size - 1]) {

if (lowerHalf.size() > higherHalf.size() + 1) {
}
} else {

if (higherHalf.size() > lowerHalf.size() + 1) {
}
}
if (size % 2 == 1) {
if (higherHalf.size() > lowerHalf.size()) {
median = higherHalf.peek();
} else {
median = lowerHalf.peek();
}
} else {
median = (lowerHalf.peek() + higherHalf.peek()) / 2;
}
System.out.print(median + " ");
}
}

}```

### Python Code For Two Heaps

```from queue import PriorityQueue

INT_MAX = 10000000000

def findMedian(arr, n):
lowerHalf = PriorityQueue()
higherHalf = PriorityQueue()
for size in range(1, n + 1):

x = INT_MAX
if lowerHalf.qsize() > 0:

x = abs(lowerHalf.get())
lowerHalf.put(-x)

if lowerHalf.qsize() > 0 and x > arr[size - 1]:
lowerHalf.put(-(arr[size - 1]))

if lowerHalf.qsize() > higherHalf.qsize() + 1:
higherHalf.put(abs(lowerHalf.get()))

else:

higherHalf.put(arr[size - 1])

if higherHalf.qsize() > lowerHalf.qsize() + 1:
lowerHalf.put(-(higherHalf.get()))

if size % 2 == 1:

if higherHalf.qsize() > lowerHalf.qsize():

median = higherHalf.get()
higherHalf.put(median)

else:

median = abs(lowerHalf.get())
lowerHalf.put(-median)

else:

a = lowerHalf.get()
lowerHalf.put(a)
b = higherHalf.get()
higherHalf.put(b)

median = (abs(a) + b) // 2

print(median, end=" ")```

Time Complexity: O(NlogN), where N is the number of elements.
Space Complexity: O(N), for storing lists.

## FAQs

Q. What is a median?
A. The median is the middle value of a sorted list of integers. If the size of the list is even, the median is the average of the two middle elements.

Q. What is the most efficient approach to solving this problem?
A. The approach using a min-heap and max heap is the most efficient approach to solve the problem. The time complexity is O(logN) and the space complexity is O(N).