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.
i guess Im randomly asking but does any of you know a way to log back into an instagram account? I was dumb forgot the login password. I would love any help you can give me!
*THE IMPLEMENTATION CAN BE MADE A LOT MORE SIMPLIER- * class MedianFinder { public: priority_queue maxheap; //1st half -> in case odd size of the total stream, the extra ele will be in the left half (max-heap) priority_queue 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 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() : (maxheap.top()+minheap.top())/2.0; } }; 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, AMAZINGGGGGGGGGGGGG EXPLANATION....
yes, it can be simplified as you said, even i also have thought the same. These videos are really useful and good explanation for all the possible cases. while inserting the element into min or max heap, check the below conditions. o if max heap size is 0, then insert the element into max heap o if max heap and min heap size are same, then if num < max heap root then • insert into max heap if num > max heap root then • pop the min heap root • insert that popped one into max heap • insert the num into min heap o else [ if max heap = 1 + min heap size, no need to check ] num < max heap root • pop the max heap root • insert the popped one into min heap • insert the num into max heap num > max heap root • insert into min heap o if max heap < min heap size [ this will never be the case ]
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?
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 (
we can make it even shorter.... . void addNum(int num) { int l=maxh.size(),r=minh.size(); if(l==r) maxh.push(num); else minh.push(num); if(r!=0) { if(maxh.top()>minh.top()) { int a=maxh.top(),b=minh.top(); maxh.pop(); minh.pop(); maxh.push(b); minh.push(a); } } }
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 :)
Hi Surya, May I ask How to answer before follow ups for this question? If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Bucket sort is one way for small range questions. Keep 100 buckets for all the values for the second follow up keep 101 buckets one extra bucket for all the values greater than 100 keep them sorted as they are just 1% sorting them won't be costly. Read about bucket sort and try to apply here you will get the intuition.
Do you have an account on Instagram? You can promote it there. I will also share your videos on my profile. I know I don't have much followers but 'something is better than nothing' Right?
And also can you show your profiles of Codechef or CodeForces or other coding platforms on which you are doing Competitive Programming in upcoming video? Because all the people are interested in numbers only. So it will help you to grow up your channel 🤟🏻
in case of else condition you have made an extra check by checking if size of min heap == 0 and then followed by condition I think that is extra not required to do that and also it is confusing
Does practice is a only solution to get the solution of such problems? It is very hard to guess the best solution of such problems without getting hints.
Practice obviously helps. But there are other factors like how well you understand a problem statement and how much you enjoy doing this as well as guidance.
Isn't nlogn the same time complexity keeping a vector, and then sorting it at time of calculating median? wouldn't it be easier and equivalent in time complexity? also how is it possible to have maxHeap size >1 and minheap size >0, i thought your goal was to keep maxHeap greater by 1 or equal to min heap size? therefore you cannot push directly to minHeap for this scenario?
We can directly use the underlying vector used for min heap. Since we know the heap size, we can fetch the middle element(s) in O(1). Can you please suggest what's the issue with this approach?
if still anyone having problem to understand this, i'll highly recommend you to watch Keerti Purswami's video. You will definitely understand and also the code is too short compared to this one.
add function can be made shorter void addNum(int num) { int l=maxh.size(),r=minh.size(); if(l==r) maxh.push(num); else minh.push(num); if(r!=0) { if(maxh.top()>minh.top()) { int a=maxh.top(),b=minh.top(); maxh.pop(); minh.pop(); maxh.push(b); minh.push(a); } } }
No need to make the third else condition that large: void addNum(int num) { int lsize = maxheap.size(); int rsize = minheap.size(); if(lsize==0){ maxheap.push(num); }else if(lsize == rsize){ int rtop = minheap.top(); if(num > rtop){ minheap.pop(); maxheap.push(rtop); minheap.push(num); }else{ maxheap.push(num); } }else{ int ltop = maxheap.top(); if(num > ltop){ minheap.push(num); }else{ maxheap.pop(); minheap.push(ltop); maxheap.push(num); }
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.
Woww ❤️ congratulations 🎉
Bhai kaise mili intuit m intern?
i guess Im randomly asking but does any of you know a way to log back into an instagram account?
I was dumb forgot the login password. I would love any help you can give me!
@@jettdexter6719 try forget password dude
@@CodeSuccessChronicle it's a bot
For the first time in almost 6 months finally we see a face behind the voice that has been guiding me in coding.
😅
@@techdose4u Saying hello from Asansol, your neighbouring city
*THE IMPLEMENTATION CAN BE MADE A LOT MORE SIMPLIER- *
class MedianFinder {
public:
priority_queue maxheap; //1st half -> in case odd size of the total stream, the extra ele will be in the left half (max-heap)
priority_queue 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 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() : (maxheap.top()+minheap.top())/2.0;
}
};
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, AMAZINGGGGGGGGGGGGG EXPLANATION....
Very Nicely explained!! 🙏🏼
yes, it can be simplified as you said, even i also have thought the same.
These videos are really useful and good explanation for all the possible cases.
while inserting the element into min or max heap, check the below conditions.
o if max heap size is 0, then insert the element into max heap
o if max heap and min heap size are same, then
if num < max heap root then
• insert into max heap
if num > max heap root then
• pop the min heap root
• insert that popped one into max heap
• insert the num into min heap
o else [ if max heap = 1 + min heap size, no need to check ]
num < max heap root
• pop the max heap root
• insert the popped one into min heap
• insert the num into max heap
num > max heap root
• insert into min heap
o if max heap < min heap size [ this will never be the case ]
For the first time, I came to know about real life use of insertion sort.. Thank you Sir !! Great explaintion...
Welcome :)
Mujhe nhi lagta TH-cam pe Striver aur TechDose se jyada achaa coding ke liye koi channel h........YOU ARE THE GEM❤
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?
Thanks. Sure
Thank you for this nice explanation. I visited different sites to solve this question. Your solution is very simple and efficient to understand.
Great explanation to this hard problem. Lot of companies ask this one.
Yea. It's very important :)
@@techdose4u amazon asked me this and i was totally clueless now i know y i was clueless
Amazing explanation! It would have helped even more if you could discuss the follow up in the question as well!
Hmmm....I somehow missed the follow-up I guess :O
Really amazing explaination, hands down one of the best dsa teacher on yt.
Best Explaination on youtube!
2 days to complete this course. Thank you for your valuable lesson.
Great video, and great questions as well during the switch from brute to optimal! Loved it, thanks :)
This channel deserves 1M subs!
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 (
we can make it even shorter....
.
void addNum(int num) {
int l=maxh.size(),r=minh.size();
if(l==r) maxh.push(num);
else minh.push(num);
if(r!=0)
{
if(maxh.top()>minh.top())
{
int a=maxh.top(),b=minh.top();
maxh.pop();
minh.pop();
maxh.push(b);
minh.push(a);
}
}
}
Thanks for the wonderful explination
No words for you , only I want to say ......................You are Diamond .......................
Thanks :)
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 :)
Sure bro :)
Watched the entire heap series. can i hope for more series like this
Yes
Awesome. Just when you said devide them jnto 2 halve, immediately it became easier.
Why can't we use binary search to insert?
It will also work with same nlogn complexity, right?
We can simply use binary search for each element for insertion right?? like bisect. Correct me if I am wrong / missing out something.
Thank you for this Amazing Video Sir
Nice explanation sir...thanks a lot for the video
I'm the 250th like. you deserve more keep it up
Thanks :)
Hi Surya, May I ask How to answer before follow ups for this question?
If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Let me check the follow ups. Dint see that to be honest.
Bucket sort is one way for small range questions. Keep 100 buckets for all the values for the second follow up keep 101 buckets one extra bucket for all the values greater than 100 keep them sorted as they are just 1% sorting them won't be costly. Read about bucket sort and try to apply here you will get the intuition.
Best Explanation. Hats off you.
Thank you for helping out so much, please do sql also
Let's see after DSA course.
What a beautiful explanation !❤️ Thank you Bhaiya again...
Welcome 😀
You are really doing an awesome job sir. May God bless you!!!!
the best solution ever !!
You're my hero man.
Great Explanation.!
Thank you for such a great explanation
Welcome 😀
What an amazing explanation!🤩 Hats off to you🙌🏻
Thanks :)
I don't know why your channel is not getting a proper growth!!! Such an amazing series of videos. But no one is sharing your content.
Do you have an account on Instagram? You can promote it there. I will also share your videos on my profile. I know I don't have much followers but 'something is better than nothing' Right?
And also can you show your profiles of Codechef or CodeForces or other coding platforms on which you are doing Competitive Programming in upcoming video? Because all the people are interested in numbers only. So it will help you to grow up your channel 🤟🏻
very nice sir thank you so much
Hi,thanks, i liked your explanation @17:00
Thanks :)
Great teaching!
Thanks 😊
great explanation
This dude is awesome
thanks for your explanation, sir this is really good .
perfect Explanation
can we use quick select algorithm for findinding mid or kth element in unordered array
You can. But still it will be too expensive and doesn't go well with stream.
Good solution
It took 3.01seconds for me. Not sure if I wrote a good code. Did it take the same time for you also? or even less?
Thank you so much.
Welcome
Hey , we can use multiset as well
I dint try that. You can try once :)
Why, quick sort algorithm is not used (at the position of insertion sort)
very well, oh wait , Awesome explanation
in case of else condition you have made an extra check by checking if size of min heap == 0 and then followed by condition I think that is extra not required to do that and also it is confusing
Does practice is a only solution to get the solution of such problems? It is very hard to guess the best solution of such problems without getting hints.
Practice obviously helps. But there are other factors like how well you understand a problem statement and how much you enjoy doing this as well as guidance.
nice explanation bro keep the work going
Thanks
Thanks
Welcome :)
Nice explanation
Thanks
Isn't nlogn the same time complexity keeping a vector, and then sorting it at time of calculating median? wouldn't it be easier and equivalent in time complexity? also how is it possible to have maxHeap size >1 and minheap size >0, i thought your goal was to keep maxHeap greater by 1 or equal to min heap size? therefore you cannot push directly to minHeap for this scenario?
no that would be n^2logn time because in that case you would be sorting n time n numbers and that would be n*(nlogn)
could code own my own after the explanation. you explain really well
🔥
We can directly use the underlying vector used for min heap. Since we know the heap size, we can fetch the middle element(s) in O(1). Can you please suggest what's the issue with this approach?
great explaination
Thanks! Keep up the good work!😃
Can we use multiset here
excellent
Good explenation
Thanks
Beautiful question and superb explanation ❤
Thanks :)
Sir please do a video on this problem: Median of Two Sorted arrays
Just a feedback that, In the last else condition, we don't need so many conditions
if still anyone having problem to understand this, i'll highly recommend you to watch Keerti Purswami's video. You will definitely understand and also the code is too short compared to this one.
Nice❣️
:)
thank u sir
amazing , smooth
thanks sir
nice explaination sir.... but the code is too complex to understand
Sir I like your face Cam. 😍
But It would be great, if increase size of your face and have green screen at ur back.
Thanks Sir
what if we use avl tree??
My according median for odd number is (n+1)/2
👍🏼
Leetcode 480 (Sliding Window Median), please !!
👍🏼
Waiting for hashing and recursion ❤️
👌🏼
love babbar has explained this better
supeeeeeeerb
hum n^(2)logn approach se dil todke iha pe ata hai
I feel last condition is extra
Question 295 has 295 likes right now lol!
😂
this one is hard.
add function can be made shorter
void addNum(int num) {
int l=maxh.size(),r=minh.size();
if(l==r) maxh.push(num);
else minh.push(num);
if(r!=0)
{
if(maxh.top()>minh.top())
{
int a=maxh.top(),b=minh.top();
maxh.pop();
minh.pop();
maxh.push(b);
minh.push(a);
}
}
}
No need to make the third else condition that large:
void addNum(int num) {
int lsize = maxheap.size();
int rsize = minheap.size();
if(lsize==0){
maxheap.push(num);
}else if(lsize == rsize){
int rtop = minheap.top();
if(num > rtop){
minheap.pop();
maxheap.push(rtop);
minheap.push(num);
}else{
maxheap.push(num);
}
}else{
int ltop = maxheap.top();
if(num > ltop){
minheap.push(num);
}else{
maxheap.pop();
minheap.push(ltop);
maxheap.push(num);
}
}
}
you can follow this too: class MedianFinder {
public:
priority_queuemaxHeap;
priority_queueminHeap;
MedianFinder() { }
void addNum(int num) {
maxHeap.push(num);
minHeap.push(maxHeap.top());
maxHeap.pop();
if(minHeap.size()>maxHeap.size()){
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if(maxHeap.size()>minHeap.size()) return double(maxHeap.top());
else return (double(maxHeap.top())+ double(minHeap.top()))/2;
}
};
great explanation
Thanks
Thanks
Welcome