Find Median from Data Stream

This video explains how to find median in a data stream.In this problem, given a stream of integers we are required to find median at any given point in a running integer also known as stream of integers.I have explained the problem with intuitive examples and i have also shown all the required intuition for solving the problem.I have first solved it using simple solution using sorting technique which is insertion sort.Later, I have shown the intuition for optimization and solved using 2 heaps. One maxheap containing left half values and the other as minheap containing the right half values of the ordered array.We can find median in constant time using the formula as I have shown for ODD and EVEN number of elements.

CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

======================================PLEASE DONATE=============================
==============================================================================

=======================================================================
USEFUL LINKS:

RELATED LINKS:

#heap #datastream #2heaps

[atishaysrivastava]

Hey thanks for uploading, I have requested this video in previous video and yesterday I got intern offer from Intuit. Thanks to you ❤️.
Everything you explain are too good to grab and follow-up.

[ashishkumarchoubey]

For the first time in almost 6 months finally we see a face behind the voice that has been guiding me in coding.

[Mr_SSK]

*THE IMPLEMENTATION CAN BE MADE A LOT MORE SIMPLIER- *


class MedianFinder {
public:
priority_queue<int> maxheap; //1st half -> in case odd size of the total stream, the extra ele will be in the left half (max-heap)
priority_queue<int, vector<int>, greater<int>> minheap; //2nd half

MedianFinder() {

}

void addNum(int num) {
int lsize = maxheap.size();
int rsize = minheap.size();

if(lsize==0) maxheap.push(num); // the right-half is surely empty -> so, num is the 1st element in stream -> store it in the first half
else if(lsize==rsize) { // as the max-heap can take one extra element -> So, ONE element will go on first half (BUT, NOT NECESSARILY 'NUM')
if(num<minheap.top()) maxheap.push(num); // when num<miHeap.top(), num can be pushed into the maxHeap -> No Violation
else { // Otherwise, shift the minHeap.top() to the maxHeap, and push the 'num' in minHeap
int temp = minheap.top(); minheap.pop();
maxheap.push(temp);
minheap.push(num);
}
}
else { // lsize!=0, and lsize!=rsize -> that means lsize>rsize. So, one element will surely be inserted in right side (BUT, NOT NECESSARILY 'NUM')
if(num>maxheap.top()) minheap.push(num); // when num>maxHeap.top(), it will obviously go on the right-side -> No Violation
else{ // Otherwise, we need to shift the maxHeap.top() to the minHeap, and push the 'num' in maxHeap
int temp = maxheap.top(); maxheap.pop();
maxheap.push(num);
minheap.push(temp);
}
}
}


double findMedian() {
int totSize = maxheap.size() + minheap.size();
return totSize%2==1? maxheap.top() :
}
};


EXPLANATION IN SIMPLE WORDS-

-> We divide the entire array into two halves, and there can be two cases -
- In case of ODD size, the maximum element from the left side will be the mediun (as we keep one extra element in the left side)
- In case of EVEN size, the average of 'maximum from left' and 'minimum from right' will be the mediun
-> In order to maintain the max and min from both the sides respectively we can use maxHeap for the left-side (as the root will hold the max),
and minHeap for the right-side (as the root will hold the min)

BUT, WHEN TO INSERT IN WHICH SIDE?
-> There can be 3 major cases-
1. When both the sides are empty - Insertion will take place in left side for sure
2. When both the sides have equal elements (but, not 0) - One element will surely be inserted in left-side as we keep one extra element in
left side, BUT not necesarily the current element. There will be 2 cases-
- when the current element is lesser than the minimum of right-side, the current element will surely be inserted in left-side, as there's
NO VIOLATION
- Otherwise, shift the minHeap.top() to the maxHeap, and push the 'num' in minHeap (to maintain the overall ordering)
3. When left-side already have one extra element - in this case one element will surely be inserted in right-side, BUT not necessarily the
current one. There will be 2 cases-
- if the current element is greater than the maximum of left-side, then obviously the current element will be placed in the right-side (No
Violation)
- Otherwise, we need to shift the maxHeap.top() to the minHeap, and push the 'num' in maxHeap

TC: O(N*logN), as it takes O(logN) for the operations in HEAP
SC: O(N), as we store the elements in HEAP*/



ANYWAYS, EXPLANATION....

[theghostwhowalk]

Great explanation to this hard problem. Lot of companies ask this one.

[lalit]

For the first time, I came to know about real life use of insertion sort.. Thank you Sir !! Great explaintion...

[NatureLover-oquc]

Mujhe nhi lagta Youtube pe Striver aur TechDose se jyada achaa coding ke liye koi channel ARE THE GEM❤

[nipunaggarwal]

Just completed this Heap Series. You are just amazing. Recommended your channel to all my friends. Sir, is deque important for interviews? If so, can you also please make a series on deque also?

[DeepakKumar-ychr]

No words for you, only I want to say are Diamond

[abhisheksrivastav]

Thank you for this nice explanation. I visited different sites to solve this question. Your solution is very simple and efficient to understand.

[Rahul-rphk]

Amazing explanation! It would have helped even more if you could discuss the follow up in the question as well!

[ismail]

Watched the entire heap series. can i hope for more series like this

[gandhijainamgunvantkumar]

I think in the else part of the addNum function, we don't have to write that many conditions, as we know that the maxheap size is 1 greater than minheap size, hence we must insert the element such that after the insertion maxheap.size() will be same as minheap.size().

So here we just have to check whehter num is less than or equal (<=) to maxheap.top().It it is less than or equal(<=) then we must insert in the maxheap. hence we will just remove the top element of maxheap and insert it into the minheap.


Now if the num is greater than maxheap.top(), then we just add the element into the minheap as we are sure that it is greater than all the elements of the maxheap.

the code is accepted on leetcode and is as following:

class MedianFinder {
public:
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;

MedianFinder() {
//as we don't have to initialize anything we don't write anything in this
}

void addNum(int num) {
int lsize = maxheap.size();
int rsize = minheap.size();

if(lsize == 0){
maxheap.push(num);
}

else if(lsize == rsize){
if(num < minheap.top()){
maxheap.push(num);
}
else{
int temp = minheap.top();
minheap.pop();
minheap.push(num);
maxheap.push(temp);
}
}

else{ //maxheap size is 1 greater than minheap size
if(num <= maxheap.top()){
int temp = maxheap.top();
maxheap.pop();
maxheap.push(num);
minheap.push(temp);
}
else{
minheap.push(num);
}
}
}

double findMedian() {
int lsize = maxheap.size();
int rsize = minheap.size();

if(lsize > rsize ) return maxheap.top();
else{
return
}
}
};

[aadityasharma]

Really amazing explaination, hands down one of the best dsa teacher on yt.

[anikkhan]

Really nice man! The questions you put to improve over the brute force algo are really crucial to understand the intuition. Thanks Sir. Plz consider doing more leetcode :)

[aryanmaniyar]

Great video, and great questions as well during the switch from brute to optimal! Loved it, thanks :)

[paragroy]

Nice explanation sir...thanks a lot for the video

[SurajKumar-vojf]

Thank you for helping out so much, please do sql also

[minhthuan]

2 days to complete this course. Thank you for your valuable lesson.

[AR-scorp]

Awesome. Just when you said devide them jnto 2 halve, immediately it became easier.

[vaishnavichilukuri]

Why can't we use binary search to insert?
It will also work with same nlogn complexity, right?