Thank you for giving such a simple explanation. I am a pre final year engineering student and I watched this video a few weeks earlier. The same question was asked to me in my technical interview yesterday when I sat for internship and the interviewer was really impressed with the way I explained it. I secured an internship there and this question has a big role in it. Thank you so much. Before watching this video I had no idea how to do this but your explanation made it really simple. I have watched your other videos as well. The way you explain is really amazing. Thanks again :)
I do not know how to say it but 1 week back I saw this video i just understood it and even did not write the code yesterday this question was asked in Walmart interview and i just explained it and got selected too..thanks to you di :) :)
This is by far the most intuitive and understandable solution on internet. The typical solution provided by leetcode is confusing and difficult to follow. Thanks for this video and keep up the good work!
I liked the way you are increasing confidence of those viewers who are unable to understand by using punch lines such as : "if it is still not clear, it is ok we will go through example and see!" That's something cool mam Thanks for such Amazing video 😀😀
I have struggled with these questions myself in the past. I know how overwhelming it can be. So I tru my best to keep it simple and keep viewers motivated ❤️
For people like me, the core concept here is to use max heap to store the left half (of sorted elements) and min-heap to store the right part (of sorted elements). So as to get the maximum of left part and minimum of right part (because we only need the middle section if we arrange elements in sorted order). 8:14 onwards, Keerti explains why we need to do that... Precise content, kudos to you!
Preparing for my interviews. The best thing about Keerti is she keeps encouraging that is even if you haven't understood then she is going to explain it even further. That helps me keep going and not close the video. Also, the explanation is very well done. Thanks Keerti 💛💛💛
The best explanation ever. I was stuck in this question from past two days and then I watched ur video..omg I solved it with in an half an hour 🔥 Though some bugs were there in my code before 😂😂😂
Lovely explanation Keerti. Great job! One suggestion though, you seem to be not caring about the code implementation (from what you said and from your past videos). That is understandable as when we reach an advanced level, an algo is all we need and a proficient coder will have no problem converting the algo to code even while they are drunk. But isn't your channel for beginners ? I can tell you code is everything for a beginner! What does one do with the algo if they can't implement it ? It would have taken you a few mins and people would have got clarity to how to convert all this "English" into actual working code. "priority_queue mypq" - Oh! that's how u implement it in code". Means the world! I guess it's a lot more hardwork ? But to be honest, most books, videos do exactly what you're doing. They just explain the algo. But if there's a beginner listening to this (which I assume is your target audience, since you break down the problem so nicely into understandable chunks) therefore isn't it obvious that they will not know how to implement a pqueue in C++ (or Java etc) ? When I was learning all this, the biggest pain point was that everyone would talk about the algo, but no one would show the code! If you show, the actual code - half the concept is clear from there itself! It is ek teer do shikaar - you can do a dry run of the algo through the code as well, and the viewer gets to see the implementation. Otherwise, I feel it is more like just hand waving in the air (again - only for beginners!). I understand looking up code is just a Google search away, but then so is looking up the algo, isn't it ? :p. Please don't take it as criticism. It is only a suggestion. I think you're doing a fantastic job! You don't have to listen to me. Thanks for another lovely vid again! :)
Hi Vishnu, thank you so much for your comment. Such discussions are always welcome :) As you said, the channel is for beginners and that is the reason I don't want to make any beginner feel that they should be restricted to one particular language. Suppose I told the syntax in C++ or java, and someone who codes in python asks why I didn't cover his language - what will I tell him/her? Infact, in most of the companies, language doesn't matter, as long as you are able to write the algorithm which I did. Also, yes both algorithm and syntax are a Google away but syntax is about copy pasting (or remembering) but algorithm is about understanding the concept behind it. I want to encourage people to go behind the logic. The syntax is something that you can just copy paste. And about Dry run, I did it for the code I wrote yeah? The only thing I didn't write was how to declare the priority queue 😅 I hope I make sense?
@@KeertiPurswani i like your way of explanation. By dividing into chunks. I agree to the point (not giving code). You make me clear in algorithm. Converting into code is jst syntax thing. P.S : we have to do some hardwork to learn something. P.P.S : if possible create telegram channel. So we can discuss there. ThankYou
You explain so calmly and nicely. Absolutely what I required. Thank u so much for making these videos. Even if some other videos are shorter, I would still prefer yours.
Your explanation was awesome. This is the C++ implementation. (I have used integer priority queue, but we can also use double.) #include using namespace std; int main() { //code int n; cin>>n; priority_queue maxheap; //Lower Half priority_queue minheap; //Upper Half int a; while(n--) { cin>>a; if(maxheap.empty() || maxheap.top()>a) { maxheap.push(a); } else minheap.push(a);
@@AK-yb4ml Yes, if input is vector you can modify the program accordingly to take input as a stream. If input is a vector you can run a loop and instead of using variable a you will write v[i] if v is your vector.
Great explanation Keerti, most of your content is very clear, concise and can be understood even by newbie's. You are the true inspiration, motivator and very good mentor to most techie's
I was practicing this question on geeksforgeeks but couldn't understand the explanation given there. So after searching for a video on youtube, I found yours and completely understood the logic. Thank you for making this video! I've subscribed to your channel 😊
thanks for sharing such gem on youtube I must say this you made this hard level problem like an easy solution NOTE : in c++ you've max priority queue by default so to make a min priority queue just multiply -1 with the element while pushing or popping from a queue once again thank you so much dii ;)
Keerti your lecture is so beautiful. Soft and clear explanation. You combined two of the best things of this world, beauty and brilliance. So i rate you as b++.
hey good that you mentioned insertion sort. We never think of quadratic sorts while giving out a brute force approach. I think its a good way to start at an interview.
@@KeertiPurswani yes I have started watching of them. You have put a lot of effort in making quality content. Great work and thanks for your contributions. Its really helpful.
Awesome, the logic can be further simplified, if you push to maxheap and then poll the top value from maxheap and push it to minheap. Maintain the difference between size to max one.
This question is quite simple to understand and to implement. If you really want to show your algorithms skills you should do a video on median of two sorted arrays in log(n) time. I'm quite sure you wouldn't be able to.
Time Complexity is 3.logn(At worst case we perform 2 push and 1 pop) and not nlogn please correct me if I am wrong, We should not consider n as the size of the array as it is a running stream.
Thanks for the explanation The solution is overall good but i personally could not wrap my head about how i will explain this approach to the interviewer as when you explained how we are inserting the number in our heaps as that is difficult to come up with on our own instead i think we should proceed by taking different cases and add number by comparing them to the current median and maintaining the size difference.
Good work! Just for the sake of completeness, I want to add some additional insights, please feel free to correct me if I got anything wrong. The main advantage of this approach is that it improves the time complexity for retrieving the median for a read heavy system in the presence of stream data. The time to retrieve max/min from priority queue is constant. Thus, the time to calculate the median from a stream of data is reduced to constant time. Pause to think about it, this is a big deal! Hadn't we use this arrangement for storing the numbers, the alternatives are really, saving the numbers in a sorted fashion in some form of set or vector. Vector is not the right choice since the input is large and we might keep resizing the vector to fit elements. In the worst case the vector keeps growing and bottlenecks the system, alternately we could chunk the array and put it in memory that has its own drawback (finding median in K sorted arrays :() The time complexity of retrieving median from a sorted structure is log N (if the structure has say N elements) and in a read heavy system, if I keep making calls to compute median a large number of time (say K) the overall complexity to calculate the median increases to KlogN or NlogN! The approach that Keerti pointed out reduces it constant time! If you have made this far, thankyou! Brownie insight...we can get the median by not really saving all the elements. We can think of equal fractions of elements we can eleminate from the heap and still get median in constant time. Illustration (for a sorted array size > 4) a1 , a2 , a3 .... ak, ak+1...aN-3, aN-2, aN-1 Can you convince yourself that the median won't change if I knock of (a1 and aN-1) and inductively if I knock off (a1, a2, aN-2 and aN-1)?? Food for thought? What else will you gain by this approach for a system that only need median and not the data really? Once again! Good job Keerti, great content, just wanted to add some more insights for completeness.
Thanks Keerti. It was well explained. Need your help with one question. I solved it in O(n) time and space complexity but when I looked out for the solution it was solved in O(nlogn) time and O(n) space complexity. Just need to verify whether my approach is correct or not. "Write a function to count number of smaller elements on right of each element in an array. Given an unsorted array arr[] of distinct integers, construct another array countSmaller[] such that countSmaller[i] contains count of smaller elements on right side of each element arr[i] in array."
@@KeertiPurswani Below mentioned is my approach. Please note I am assuming input array contain distinct integers. 1. Consider "nums" as your input array and "result" as your final output array. 2. Take another array "nextSmaller" with size the same as of nums. 3. nextSmaller[i] stores index of element which is present on right of nums[i] and is just smaller than nums[i]. If no smaller element exists to right of nums[i] then nextSmaller[i] = -1. 4. result[n-1] = 0 where n is size of input array. 5. for j=n-2 to 0 result[j] = nextSmaller[i] != -1 ? result[nextSmaller[i]]+1 : 0;
Your explanation is soo good, I am able to write code by myself, But I want to know why we dont simply use vector O(1) and find mid element with help of Quick Serach O( Nlog(mid) ).
The numbers come in a potentially endless stream. You would have to do quick sort every time you need to find the median. The insert sort would keep the list ordered, making it cheap to find the median at any time, but it's still slower than this maxheap/minheap solution.
@@KeertiPurswani Your explanation was very clear. I implement everything in code. And got AC. But i feel if you provide link to code. It is awesome. ThankYou..
@@nagavijaykumarprathi8531 I try to explain in the way that one can write the code, like you did 😊 if I write code in a language, it will restrict viewers mind to that language and I really don't want to do that!
Thank you for giving such a simple explanation. I am a pre final year engineering student and I watched this video a few weeks earlier. The same question was asked to me in my technical interview yesterday when I sat for internship and the interviewer was really impressed with the way I explained it. I secured an internship there and this question has a big role in it. Thank you so much. Before watching this video I had no idea how to do this but your explanation made it really simple. I have watched your other videos as well. The way you explain is really amazing. Thanks again :)
This made my day!
Thank you so Aman 🙂 Congratulations and all the best for your internship 😇😇
@@KeertiPurswani Thanks :)
I do not know how to say it but 1 week back I saw this video i just understood it and even did not write the code yesterday this question was asked in Walmart interview and i just explained it and got selected too..thanks to you di :) :)
Congratulations Sameer. So happy for you!!❤️
And thank you for sharing with me 😇
This is by far the most intuitive and understandable solution on internet. The typical solution provided by leetcode is confusing and difficult to follow. Thanks for this video and keep up the good work!
I liked the way you are increasing confidence of those viewers who are unable to understand by using punch lines such as : "if it is still not clear, it is ok we will go through example and see!" That's something cool mam Thanks for such Amazing video 😀😀
I have struggled with these questions myself in the past. I know how overwhelming it can be. So I tru my best to keep it simple and keep viewers motivated ❤️
@@KeertiPurswani You're too kind :') thank you so much for the SUPER smooth explanation
For people like me, the core concept here is to use max heap to store the left half (of sorted elements) and min-heap to store the right part (of sorted elements). So as to get the maximum of left part and minimum of right part (because we only need the middle section if we arrange elements in sorted order).
8:14 onwards, Keerti explains why we need to do that...
Precise content, kudos to you!
Thanks Ritik 😇😇
Loved it! Never seen someone explaining a hard level question so calmly and intuitively ! Thank you keerti 👏👏👏
Itna preshan hone ke bad abh is video ko dekhne ke bad code smjh aya !
Thank you For such a clear , calm and Intuitive Solution.
Preparing for my interviews. The best thing about Keerti is she keeps encouraging that is even if you haven't understood then she is going to explain it even further. That helps me keep going and not close the video.
Also, the explanation is very well done. Thanks Keerti
💛💛💛
Best and fluid explanation. Even in the first 5 minutes got the intuition and the next explanations are cherry on top. Thanks again.
Your explanation skills are top notch. A calm river slowly flowing out to the sea . Same rythm smooth flow
The best explanation ever. I was stuck in this question from past two days and then I watched ur video..omg I solved it with in an half an hour 🔥
Though some bugs were there in my code before 😂😂😂
Lovely explanation Keerti. Great job! One suggestion though, you seem to be not caring about the code implementation (from what you said and from your past videos). That is understandable as when we reach an advanced level, an algo is all we need and a proficient coder will have no problem converting the algo to code even while they are drunk. But isn't your channel for beginners ? I can tell you code is everything for a beginner! What does one do with the algo if they can't implement it ? It would have taken you a few mins and people would have got clarity to how to convert all this "English" into actual working code. "priority_queue mypq" - Oh! that's how u implement it in code". Means the world! I guess it's a lot more hardwork ? But to be honest, most books, videos do exactly what you're doing. They just explain the algo. But if there's a beginner listening to this (which I assume is your target audience, since you break down the problem so nicely into understandable chunks) therefore isn't it obvious that they will not know how to implement a pqueue in C++ (or Java etc) ? When I was learning all this, the biggest pain point was that everyone would talk about the algo, but no one would show the code! If you show, the actual code - half the concept is clear from there itself! It is ek teer do shikaar - you can do a dry run of the algo through the code as well, and the viewer gets to see the implementation. Otherwise, I feel it is more like just hand waving in the air (again - only for beginners!). I understand looking up code is just a Google search away, but then so is looking up the algo, isn't it ? :p.
Please don't take it as criticism. It is only a suggestion. I think you're doing a fantastic job! You don't have to listen to me. Thanks for another lovely vid again! :)
Hi Vishnu, thank you so much for your comment. Such discussions are always welcome :)
As you said, the channel is for beginners and that is the reason I don't want to make any beginner feel that they should be restricted to one particular language. Suppose I told the syntax in C++ or java, and someone who codes in python asks why I didn't cover his language - what will I tell him/her?
Infact, in most of the companies, language doesn't matter, as long as you are able to write the algorithm which I did.
Also, yes both algorithm and syntax are a Google away but syntax is about copy pasting (or remembering) but algorithm is about understanding the concept behind it.
I want to encourage people to go behind the logic. The syntax is something that you can just copy paste.
And about Dry run, I did it for the code I wrote yeah? The only thing I didn't write was how to declare the priority queue 😅
I hope I make sense?
@@KeertiPurswani i like your way of explanation. By dividing into chunks.
I agree to the point (not giving code).
You make me clear in algorithm. Converting into code is jst syntax thing.
P.S : we have to do some hardwork to learn something.
P.P.S : if possible create telegram channel. So we can discuss there.
ThankYou
@@KeertiPurswani I loved the way you handled the comment. Very camly!!
Calm and detailed explanation. Appreciate you for a quick recap every few minutes. Keep up the good work.
Glad you liked it! Thank you 😇
You explain so calmly and nicely. Absolutely what I required. Thank u so much for making these videos. Even if some other videos are shorter, I would still prefer yours.
Best explanation for this problem by dry running it, in the whole TH-cam.
Loving the success stories in the comments. You are definitely a great teacher Di !
Thank you Aakash, means so much ❤️
Success stories are my fav too😇😇
Your explanation was awesome.
This is the C++ implementation.
(I have used integer priority queue, but we can also use double.)
#include
using namespace std;
int main() {
//code
int n;
cin>>n;
priority_queue maxheap; //Lower Half
priority_queue minheap; //Upper Half
int a;
while(n--)
{
cin>>a;
if(maxheap.empty() || maxheap.top()>a)
{
maxheap.push(a);
}
else minheap.push(a);
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();
}
if(minheap.size()==maxheap.size()) cout
Great job @Akash. Thanks for sharing 😊😊
Is " a " here is running number or stream here.
If input is vector of Integers then would it give correct answer.
@@AK-yb4ml Yes, if input is vector you can modify the program accordingly to take input as a stream.
If input is a vector you can run a loop and instead of using variable a you will write v[i] if v is your vector.
Great explanation Keerti, most of your content is very clear, concise and can be understood even by newbie's. You are the true inspiration, motivator and very good mentor to most techie's
Kya hi explain kiya hai, maja aa gya. Sab samajh aa gya. 🧡 from remote.
One of the most fluid explanations of a problem that I have come across!
Thank you Utkarsh 😇
I was practicing this question on geeksforgeeks but couldn't understand the explanation given there. So after searching for a video on youtube, I found yours and completely understood the logic.
Thank you for making this video! I've subscribed to your channel 😊
Thank you so much Danish. Means a lot 😇
@@KeertiPurswani You're welcome 😊
@@KeertiPurswani same happened with me...Thanks, it really helped me a lot :)
thanks for sharing such gem on youtube I must say this you made this hard level problem like an easy solution
NOTE : in c++ you've max priority queue by default so to make a min priority queue just multiply -1 with the element while pushing or popping from a queue
once again thank you so much dii ;)
Keerti please keep going and you will be one of the best teachers in this field very soon.
This is great Keerti, proud of your hardwork!! 😍😍
Thank you so much ❤️
why you proud of her work? just curious
She is my friend 😇
@@KeertiPurswani got it!.. Very good channel for learning.. good luck!!
This question was Best explained here 👍🏼
Thank you @gaurav 😊
Mam hats off to your explanation only listening to the explanation made the code crystal clear thank you for this amazing content
Thank you for the great explanation.
Java code with stream of integers generation and finding the median is given below:
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class RunningMedian {
public static void main(String args[]) {
RunningMedianUtility runningMedianUtility = new RunningMedianUtility();
// stream of integers
IntStream.generate(() -> new Random().nextInt(50)).limit(new Random().nextInt(50)).forEach(
runningMedianUtility::add
);
//Display values of min and max heap
runningMedianUtility.display();
System.out.println(runningMedianUtility.getMedian());
}
}
class RunningMedianUtility {
private final PriorityQueue maxHeap;
private final PriorityQueue minHeap;
public RunningMedianUtility() {
this.maxHeap = new PriorityQueue((o1, o2) -> {
return -1 * o1.compareTo(o2);
});
this.minHeap = new PriorityQueue();
}
public void add(Integer value) {
if (maxHeap.isEmpty() || maxHeap.peek() > value) {
maxHeap.add(value);
} else {
minHeap.add(value);
}
// Re-balancing
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.add(minHeap.poll());
}
}
public double getMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else if (minHeap.size() > maxHeap.size()) {
return minHeap.peek();
} else {
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}
}
public void display() {
System.out.println(maxHeap.stream().map(o -> String.valueOf(o)).collect(Collectors.joining(",")));
System.out.println(minHeap.stream().map(o -> String.valueOf(o)).collect(Collectors.joining(",")));
}
}
👍great explanation! She and Jenny are the best indian women youtubers who are expert in DSA.✌
Nice explanation Keerti. I understood your approach and solved this question on leetcode watching first 10 minutes of video
Excellent, excellent, excellent explanation! Thank you for sharing this! this really helps with a hackerrank problem set
Crystal clear explanation for a supposedly hard question!
Keerti your lecture is so beautiful. Soft and clear explanation. You combined two of the best things of this world, beauty and brilliance. So i rate you as b++.
This is a very clear explanation. Good job Keerti! So proud!!!
Thanks bro❤️❤️
Wonderfully explained, not gonna forget this for the rest of my life
OMG! Thank you🙈❤️
Thank you Keerti for the amazing explanation. this is now imprinted in my mind.
The best explaination Keerti , it makes the question difficult to forget !
This is the best and the smallest possible code available 🔥🔥 and yeh best explantion thank u Ma'am
Thank You very much I watched several videos but couldn't understand but after watching this video I was able to fully understand it.
Great explanation, explained in very simple terms, can be understood for the very beginners in the programming.
Glad you liked it 😇
ohhh my god!! , what a clear understanding I got after watching this video, thanku so much mam. loved it
The Best Explanation Ever !!!
what an explanation 😲 Fantastic !!
This is the best explanation of this question i've got so far..thanks!
such shortcode for this hard level marked question was just unimaginable! looking on for more of your videos! thank you, saviour! :p
Haha yeah, it’s all about the concept!
Thank you so much for all the love and support❤️
GOD LEVEL EXPLANATION
Hard problem + best explanations = problem become a cakewalk.
Achievement unlocked 😇
Very nice explanation. Could not have cracked this approach in live interview before.
Great teaching sense and awesome explanation.... 🔥🔥🔥🔥
Thank you @Rishav 😊
No doubt this is a difficult question but, the way you explained it made this question really easy. Thank you Ma'am .
Thank you so much Tanmay 😇🙏🏻
Very Simple step by step explanation
Just one word - "Excellent"!
Very smoothly explained. Thanks Ma'am.
I appreciate your patience and calmness! Really look up to you Keerti di :)
Thank you so much Ravisha. Means a lot🙈❤️
@@KeertiPurswani ♥️
hey good that you mentioned insertion sort. We never think of quadratic sorts while giving out a brute force approach. I think its a good way to start at an interview.
Thanks Pramod 🙂
Really nice and simple explanation over youtube!!!...
Thanks Aman 😇 Hope you like rest of the videos as well 😇
@@KeertiPurswani Yes...😍
Thanks a ton didi.Providing such amazing content for free
Blessed to be able to do that 😇😇
Wonderful explanation for Heaps. Hard to find such simple explanation anywhere else.
Thank you so much Naresh. Means a lot. Hope you like rest of the videos as well 😇😇
@@KeertiPurswani yes I have started watching of them. You have put a lot of effort in making quality content. Great work and thanks for your contributions. Its really helpful.
Thank you 🥺🥺😇😇
Awesome, the logic can be further simplified, if you push to maxheap and then poll the top value from maxheap and push it to minheap. Maintain the difference between size to max one.
That's exactly what I am doing 😅 what is the simplification suggested?😅
This question is quite simple to understand and to implement. If you really want to show your algorithms skills you should do a video on median of two sorted arrays in log(n) time. I'm quite sure you wouldn't be able to.
There’s already a video on that, and don’t be so sure because everyone who watched the video can do it for sure ✌️
Thanks you for giving such a simple explanation
you explained the question soo well that now it feels like an easy problem 😄
Your explanations are easy to understand. Keep doing great work.
Thank you Ramesh, means so much❤️
well done keerti, it was really explained well....kudos!!!!!!
Loved the way you made it so simple
Unbeatable explanation .
Really great work di .
Thank you so much ❤️
she explained it beautifully . great video .
Thank you 😇😇
I could not figure out when to insert in min-heap and when to insert in max-heap(which is the most important part). Thanks for the explanation. OP :P
Please watch the video once more? I am sure you will understand!
Amazing explanation. God's work!
Best explanation ever!!!
Thank you very much
Thank you for the awesome content always.I finally understood this hard problem.Best explanation ever
Thanks Keerti. Keep your good work !
this problem doesn't look hard enough after your explanation, loved the explanation please make more videos.
Thank you so much. Many videos coming up 😇😇
This was a very easy explanation I have ever seen. Thank you
Thanks Patel, means a lot 😇😇
Haha First name is Raj 😅
Oh sorry😅😅🙈🙈
No worries 😅
Glad I found your channel !💯😍
I just Want to know what's the difference if we use a single set/heap . What will be the reduce in time complexity by using 2 heap
Time Complexity is 3.logn(At worst case we perform 2 push and 1 pop) and not nlogn please correct me if I am wrong, We should not consider n as the size of the array as it is a running stream.
Best explanation ever!
Thank you!🙏🏻😇
U made it soo easy to understand 🔥🔥🙏🏻🙏🏻🎉🎉
Yaaay, thank you ❤️❤️ hope you like rest of the videos as well 😇😇
such a clear explanation ! Thank you so much Di
Thanks Prerna. So glad you like it!
Please do share the channel with your friends and help it get better reach 😇🙏
Thanks for the explanation The solution is overall good but i personally could not wrap my head about how i will explain this approach to the interviewer as when you explained how we are inserting the number in our heaps as that is difficult to come up with on our own instead i think we should proceed by taking different cases and add number by comparing them to the current median and maintaining the size difference.
Please make more videos on such questions. We need more teachers like you..
Good work! Just for the sake of completeness, I want to add some additional insights, please feel free to correct me if I got anything wrong.
The main advantage of this approach is that it improves the time complexity for retrieving the median for a read heavy system in the presence of stream data. The time to retrieve max/min from priority queue is constant. Thus, the time to calculate the median from a stream of data is reduced to constant time. Pause to think about it, this is a big deal!
Hadn't we use this arrangement for storing the numbers, the alternatives are really, saving the numbers in a sorted fashion in some form of set or vector. Vector is not the right choice since the input is large and we might keep resizing the vector to fit elements. In the worst case the vector keeps growing and bottlenecks the system, alternately we could chunk the array and put it in memory that has its own drawback (finding median in K sorted arrays :()
The time complexity of retrieving median from a sorted structure is log N (if the structure has say N elements) and in a read heavy system, if I keep making calls to compute median a large number of time (say K) the overall complexity to calculate the median increases to KlogN or NlogN!
The approach that Keerti pointed out reduces it constant time!
If you have made this far, thankyou! Brownie insight...we can get the median by not really saving all the elements. We can think of equal fractions of elements we can eleminate from the heap and still get median in constant time.
Illustration (for a sorted array size > 4)
a1 , a2 , a3 .... ak, ak+1...aN-3, aN-2, aN-1
Can you convince yourself that the median won't change if I knock of (a1 and aN-1) and inductively if I knock off (a1, a2, aN-2 and aN-1)??
Food for thought? What else will you gain by this approach for a system that only need median and not the data really?
Once again! Good job Keerti, great content, just wanted to add some more insights for completeness.
Thanks Keerti. It was well explained. Need your help with one question. I solved it in O(n) time and space complexity but when I looked out for the solution it was solved in O(nlogn) time and O(n) space complexity.
Just need to verify whether my approach is correct or not.
"Write a function to count number of smaller elements on right of each element in an array. Given an unsorted array arr[] of distinct integers, construct another array countSmaller[] such that countSmaller[i] contains count of smaller elements on right side of each element arr[i] in array."
Hi Nishant
Please share the approach you followed. There can be multiple solutions to this question but I doubt if it is possible is O(n) time
@@KeertiPurswani Below mentioned is my approach. Please note I am assuming input array contain distinct integers.
1. Consider "nums" as your input array and "result" as your final output array.
2. Take another array "nextSmaller" with size the same as of nums.
3. nextSmaller[i] stores index of element which is present on right of nums[i] and is just smaller than nums[i].
If no smaller element exists to right of nums[i] then nextSmaller[i] = -1.
4. result[n-1] = 0 where n is size of input array.
5. for j=n-2 to 0
result[j] = nextSmaller[i] != -1 ? result[nextSmaller[i]]+1 : 0;
@@KeertiPurswani You are right. It can't be solved in O(n). Now I know where I got wrong. Thanks :)
Awesome Nishant. This is how we learn the most, learning from our own mistakes 😇😊
The explanation and dry run was awesome. Kudos to your great efforts!
Thank you @Abhishek 😊
Your explanation is soo good, I am able to write code by myself, But I want to know why we dont simply use vector O(1) and find mid element with help of Quick Serach O( Nlog(mid) ).
The numbers come in a potentially endless stream. You would have to do quick sort every time you need to find the median. The insert sort would keep the list ordered, making it cheap to find the median at any time, but it's still slower than this maxheap/minheap solution.
@@Rothron Thank You, I implemented this and find , it taking more time by using Quick Serach every time
Best explanation of the question and solution.
Thanks Shyman 😇
Great explaination. I am watching your video for the first and really liked it. Keep doing the same.
Thank you 😇😇
Best Explanation 💖
thank you for such wonderful explanation
Beautiful Explanation !!
Thank you!☺️
Mam You are doing great work . please consider more hard problems from Leetcode .
beautiful explanation!
Loved it.....
Amazing explanation of the solution. Please make more and more videos like this. Thank you.
Thank you. Many videos coming up 😊
Very good explanation! Thanks
Really great explanation. Loved it
Thank you Taniya 😊😊
Woah! Great explanation Mam...
Thanks Rajat! 😇 please do share the channel with your friends for better reach 😊
Thank you Di..
You are amazing!
Great explanation..
Love you from bottom of my heart.. 😍
If possible please provide the links to he code.
Thank you 😊😊
Which part of code do you need help with?
@@KeertiPurswani
Your explanation was very clear.
I implement everything in code. And got AC.
But i feel if you provide link to code. It is awesome.
ThankYou..
@@nagavijaykumarprathi8531 I try to explain in the way that one can write the code, like you did 😊 if I write code in a language, it will restrict viewers mind to that language and I really don't want to do that!
@@KeertiPurswani Really you explained very well.
ThankYou for your efforts. 😍
Excellent explanation in the Visualization part.
Thank you! 😇😇
Best one explanation.