# Find Median from Data Stream LeetCode Solution

Here, We see Find Median from Data Stream LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## 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.

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Output [null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.findMedian(); // return 2.0

## Find Median from Data Stream LeetCode SolutionC++

class MedianFinder {
public:
priority_queue<int, vector<int>, greater<int> > minHeap;
priority_queue<int> maxHeap;
MedianFinder(){}
if (maxHeap.empty() or maxHeap.top() > num) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}

double findMedian() {
if (maxHeap.size() == minHeap.size()) {
if (maxHeap.empty()) {
return 0;
} else {
double avg = (maxHeap.top() + minHeap.top()) / 2.0;
return avg;
}
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.top() : minHeap.top();
}
}
};Code language: PHP (php)

## Find Median from Data Stream LeetCode SolutionJava

class MedianFinder {
PriorityQueue<Integer> min = new PriorityQueue();
PriorityQueue<Integer> max = new PriorityQueue(1000, Collections.reverseOrder());
max.offer(num);
min.offer(max.poll());
if (max.size() < min.size()){
max.offer(min.poll());
}
}
public double findMedian() {
if (max.size() == min.size()) return (max.peek() + min.peek()) /  2.0;
else return max.peek();
}
};Code language: PHP (php)

## Find Median from Data Stream LeetCode SolutionJavaScript

var MedianFinder = function() {
this.maxHeap = new Heap(Heap.maxComparator);
this.minHeap = new Heap(Heap.minComparator);
};
if(this.maxHeap.peek() === null || num < this.maxHeap.peek()) {
} else {
}
if(this.maxHeap.size - this.minHeap.size > 1) {
} else if(this.minHeap.size - this.maxHeap.size > 1) {
}
};
MedianFinder.prototype.findMedian = function() {
if(this.maxHeap.size > this.minHeap.size) {
return this.maxHeap.peek();
} else if(this.maxHeap.size < this.minHeap.size) {
return this.minHeap.peek();
} else {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
}
};

class Heap {
constructor(comparator) {
this.size = 0;
this.values = [];
this.comparator = comparator || Heap.minComparator;
}
this.values.push(val);
this.size ++;
this.bubbleUp();
}
peek() {
return this.values[0] || null;
}
poll() {
const max = this.values[0];
const end = this.values.pop();
this.size --;
if (this.values.length) {
this.values[0] = end;
this.bubbleDown();
}
return max;
}
bubbleUp() {
let index = this.values.length - 1;
let parent = Math.floor((index - 1) / 2);
while (this.comparator(this.values[index], this.values[parent]) < 0) {
[this.values[parent], this.values[index]] = [this.values[index], this.values[parent]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
bubbleDown() {
let index = 0, length = this.values.length;
while (true) {
let left = null,
right = null,
swap = null,
leftIndex = index * 2 + 1,
rightIndex = index * 2 + 2;
if (leftIndex < length) {
left = this.values[leftIndex];
if (this.comparator(left, this.values[index]) < 0) swap = leftIndex;
}
if (rightIndex < length) {
right = this.values[rightIndex];
if ((swap !== null && this.comparator(right, left) < 0) || (swap === null && this.comparator(right, this.values[index]))) {
swap = rightIndex;
}
}
if (swap === null) break;
[this.values[index], this.values[swap]] = [this.values[swap], this.values[index]];
index = swap;
}
}
}
Heap.minComparator = (a, b) => { return a - b; }
Heap.maxComparator = (a, b) => { return b - a; }Code language: JavaScript (javascript)

## Find Median from Data Stream SolutionPython

class MedianFinder:
def __init__(self):
self.small = []
self.large = []