There is no way that you can come up with this optimal solution in an interview. Although the better solution using merge procedure from merge sort was pretty thinkable and doable but this is a completely genius solution !!!
I came up with it on my own when solving it on Leetcode. Let’s be honest, the main idea is not very hard. But my problem was the actual implementation. You can see in the video just how many random +1 and -1 we need, as well as boundary checks. It’s crazy. I hoped Striver would find a way to make the code less ugly - sadly, no. The problem is just inherently very annoying
I came up with different approach on this one when solving on my own. It's similar to what we do in matrix's binary search I guess ( I have not watched striver's videos on it). Basically searching for kth element in any sorted arrays. It took O( log(m*n)*log(max-min)) time complexity, pretty big but it's in log and was accepted in leetcode.
Striver you are a real social reformer. At times when colleges are rendering students unemployable , you are making us industry ready. Dude Hats off to you.
@@easylearn8924 the idea is to do a binary search over the smaller-size array. while loop is written based on that and that's why using min(n1,n2) would give you error.
@@easylearn8924 If we do that that's also possible but the code complexity will be too large and the std. while loop of binary search won't work even I understood after that video.
best video of entire playlist. I never understood this problem's binary search approach earlier, but you solved it so well. And that idea to call that function again if sizeof(b)
@@VivekKumar-p2g4lIt might possible that the first array has greater size,so in order to take the shorter array to proceed he did it, hence TC : O(log(min(n1,n2)))
I wanna know, how you built your logic and how you became an expert in understanding this logic so well. I have been following your playlist for a couple of months and understood each problem so well. What steps do you follow in your initial stage to reach this point? Please help so that your valuable tips can help me crack coding interviews. Trust me you are simply Amazing and Genius :)
@@ashish4k07 Can you please explain why did he do bit manipulation there for find mid1? I've watched almost all his previous videos up until this problem, and he hasn't explained bit manipulation yet.
at 1st I thought i wouldn't understand this, but it stick till the end and it was so clear. Amazing explanation and it so motivating to see the efforts made explaining this. Thanks a lot!!
Understood. GOod video striver. It's important to watch these important questions because it is not possible to invent these kind of solutions then and there itself.
This is the first video that I have not understood of you. No matter how many times I watch I just can't understand. I'm just skipping this optimal approach for now. :)
you just have to understand all the concept better and try to practice more problems on your own and like solve some old problems as well to strength your concepts and get motivation.
these problems are standard problems aka basic ones, no one can come up with solutions of such problems unless they are god gifted in mathematics The problems in contest are variation of such basic problem which can be solved by all if they know basic problems.
I still can't imagine how would someone think of such an optimal solution? It's out of mind. Are we expected to think of such optimal soln? I'm asking this bcz, it took me lot of time to understand this soln even after a great explanation... Thank you striver for such a wonderful explanation !
Such a thorough explanation! Exactly what I needed to help me understand this problem. Great energy throughout and the lesson was clearly well prepared and organized to educate and enlighten. Thank you!
before watching this intution , my favourite intution was dutch national flag algo,,, but this question along with its explanation was beyond my imagination,,,, hats off to you.......and your expression after completing this ques shows how passionate you are about your work and this gives us too much motivation,,,thank you😇😇
@@arjunc1482 I am not saying I will use duch algo here,,, I have just stated among all algo/intuitions duch algo and it's question was my fav,,, but after watching this question and it's soln , it is my fav now
Thanks striver to explain this . I was thinking that this is too much difficult concept but after watching this video , I can do the similar stuff myself. Thank you so much
I don’t know whether you’ll read this comment or not, but believe me bhayia, I can’t imagine how I would have studied DSA without you to teach. Thank you so much, always. ♥
If striver explains this question to a dead body and later asks him whether you understood or not. That dead body will yell from it's grave - "Understood Sir 💀☠"
I have also solved this but using another method: Approach was to iterate one smaller array from 1 to n and applying binary search and insert the element into another vector using bs.
One case that could have been discussed: That is: Can there be a case where, l1 > r2 & l2 > r1. What to do in that case? Answer: There cannot be such a case. This can be proved. So let's assume l1 > r2 & l2 > r1 & try to reach to a contradictory statement. So we know that r1 > l1 (Because array is sorted) Therefore, r2
Hi bro . Recently i started to watch your array playlist. Today i watching this median problem . I clearly understood your logic at first time itself . I really amazed with your logical thinking . How could you come up with this logic . You are making me logical thinking and programming more interesting. I am started to learn all the concept . Now i am following logic which is already there. But the way you are approaching all the problem with different optimal solution, its very unpredictable. Please provide some tips how you have build your logic on each ptogram when you started your coding journey. That would help most of the freshers. Thank you!
@takeUforward, @30.01 generally in Binary search of array we consider left =0 and right=array.size()-1 correct? But here why have you considered low =0 and high=n1 ( which is array size itself) not n1-1?
i thought of a different procedure first i will check if n1+n2 is odd or even and then proceed accordingly then i would use any vector and do a binary seach in it mid will act as a wall and if n1+n2 is odd there will be 2 walls one is mid and second is mid-1 then i would iterate between the elements of the other vector(where i have not applied the binary search) also i will count the one of elements on the left side of the walls and no of elemets on the right side of the walll then i will check for the first element of the other vector if that element is lesser than the a[low] then i will do left++ and move to the second element if it is greater than alow but lesser than wall1(basically mid-1) i will again do left++ if its greater than awall1 and smaller than awall2 then i will update the wall1 to that element and would do left++ (same can be done for right side) after iterating to all the elements in second vector i will compare the value of left and right
Great Explanation! Just one observation, while explaining solution you considered median to be r1/r2 value in case of odd total length, so left part doesn’t include median, but in coding part you have considered median to be l1/l2 which mean left part includes median. Got little confused with that.
18:43 determining how to pick the number of elements how did you comes up with this is this just observation skill ? or was there an intuition ? i dont think i would have seen such a pattern anyone knows the answer please help
There is no way that you can come up with this optimal solution in an interview. Although the better solution using merge procedure from merge sort was pretty thinkable and doable but this is a completely genius solution !!!
I came up with it on my own when solving it on Leetcode. Let’s be honest, the main idea is not very hard. But my problem was the actual implementation. You can see in the video just how many random +1 and -1 we need, as well as boundary checks. It’s crazy. I hoped Striver would find a way to make the code less ugly - sadly, no. The problem is just inherently very annoying
@@titusandronikus1337 Really glad that you were able to come with the optimal solution on your own !!!!
I came up with different approach on this one when solving on my own. It's similar to what we do in matrix's binary search I guess ( I have not watched striver's videos on it). Basically searching for kth element in any sorted arrays. It took O( log(m*n)*log(max-min)) time complexity, pretty big but it's in log and was accepted in leetcode.
@@titusandronikus1337 same thought process is thinkable but seriously the implementation is though,hoestly i didnt understand fully
@abhik6400 can u tell how it is doable from merge sort???
Striver you are a real social reformer.
At times when colleges are rendering students unemployable , you are making us industry ready.
Dude Hats off to you.
The going into recursion for swapping idea was 🔥
can you explain why he does that?? or we also use min(n1,n2) but it gives runtime error why??
@@easylearn8924 the idea is to do a binary search over the smaller-size array. while loop is written based on that and that's why using min(n1,n2) would give you error.
ok thanks@@tovenkatesh82
@@easylearn8924 If we do that that's also possible but the code complexity will be too large and the std. while loop of binary search won't work even I understood after that video.
why it won't work in while loop can you explain?? because i able to understand but after sometime i confused in this part??@@ashish4k07
He has already explained this in sde sheet but still he made a video for a2z sheet💯
On which sheet has he explained this ? can you give me the link. Thanks
@@farazahmed7maybe from his sde sheet for placements
@@farazahmed7 i think he is talking about the placement series or the sde sheet of 180 questions he made long time ago, you should check that out.
best video of entire playlist. I never understood this problem's binary search approach earlier, but you solved it so well. And that idea to call that function again if sizeof(b)
Why we need to do that ?
Can you explain
@@VivekKumar-p2g4lIt might possible that the first array has greater size,so in order to take the shorter array to proceed he did it, hence TC : O(log(min(n1,n2)))
@@VivekKumar-p2g4l he is taking the first array to be smaller
Watched both videos twice ,all 3 approaches are crystal clear now,thank you!
I wanna know, how you built your logic and how you became an expert in understanding this logic so well. I have been following your playlist for a couple of months and understood each problem so well. What steps do you follow in your initial stage to reach this point? Please help so that your valuable tips can help me crack coding interviews. Trust me you are simply Amazing and Genius :)
the tip is, its all about practice
If i hadn't checked this video there is no way i would be able to think of this solution in interview
Thanks...
Waiting for this one for a long time no one explained this problem this well , Thank you.
That swapping of the inputs and >>1 steps are 🔥 🔥
bit manupulation and swapping is to low so yeah it improves time mostly
@@ashish4k07 Can you please explain why did he do bit manipulation there for find mid1?
I've watched almost all his previous videos up until this problem, and he hasn't explained bit manipulation yet.
@@Manas-jj6xf basically >> means right shift which divides the number
This is one of the bestest explanations I have come across. Totally cleared my concept. Thanks a lot sir !
at 1st I thought i wouldn't understand this, but it stick till the end and it was so clear. Amazing explanation and it so motivating to see the efforts made explaining this. Thanks a lot!!
Understood. GOod video striver. It's important to watch these important questions because it is not possible to invent these kind of solutions then and there itself.
After watching so many videos i actually the found the gem which resolved my all the doubts in such a nice and simple way.
This is the first video that I have not understood of you. No matter how many times I watch I just can't understand. I'm just skipping this optimal approach for now. :)
I am so dumb even after solving good number of questions on leetcode I even could not even think of like this.
same same
you just have to understand all the concept better and try to practice more problems on your own and like solve some old problems as well to strength your concepts and get motivation.
these problems are standard problems aka basic ones, no one can come up with solutions of such problems unless they are god gifted in mathematics
The problems in contest are variation of such basic problem which can be solved by all if they know basic problems.
bro you get better by uderstand
Same🥲
Best video explanation of this problem on the whole internet.
Understood completely . Great man , you are God in DSA.
This is a great approach, no way I could come up with this in an interview...
I still can't imagine how would someone think of such an optimal solution? It's out of mind. Are we expected to think of such optimal soln? I'm asking this bcz, it took me lot of time to understand this soln even after a great explanation...
Thank you striver for such a wonderful explanation !
The king of coding community 👑
Such a thorough explanation! Exactly what I needed to help me understand this problem. Great energy throughout and the lesson was clearly well prepared and organized to educate and enlighten. Thank you!
You deeply understand the problem and explain the solution well. Thanks.
before watching this intution , my favourite intution was dutch national flag algo,,, but this question along with its explanation was beyond my imagination,,,, hats off to you.......and your expression after completing this ques shows how passionate you are about your work and this gives us too much motivation,,,thank you😇😇
bro..how will you use dutch national flag algo for this question?
@@arjunc1482 I am not saying I will use duch algo here,,, I have just stated among all algo/intuitions duch algo and it's question was my fav,,, but after watching this question and it's soln , it is my fav now
Thanks striver to explain this . I was thinking that this is too much difficult concept but after watching this video , I can do the similar stuff myself. Thank you so much
One of the best explanation I have seen so far👌
I shocked at the end of video after seeing the way you explained this complex optimal solution!!!!
Thanks a lot!❤🔥💥❤💯
Crystal clear explanation. Explained your heart out. Thank you :)
brilliant explanation, this problem is not only hard to do but also hard to explain
Really wonderful approach and explanation
TOP notch explanation striver. I saw both videos. Understood completerly. Thank you.
Mind Blowing Solution approach
Once again, your explanation is top-notch.
Amazing, how you observe so minutely :) Bhai Hat's Off .
brilliant explanation. even hard topics seem easy when you explain them.
Understood! Super amazing explanation as always thank you very very much for your effort!!
I don’t know whether you’ll read this comment or not, but believe me bhayia, I can’t imagine how I would have studied DSA without you to teach. Thank you so much, always. ♥
Thanku for making optimal vedio separately for this problem 🥲❣️🙌🏻
Thanks for the elegant approach! Loved it
Best video. I watched twice and understood great effort and awesome solution 🔥🔥
What a energy !
Thank you striver for amazing content 🙇
God Level Explaination sir 🔥
Explained so smoothly🔥🔥
Hats off to you Broh... THANKS A MILLION 💙💙💙
At first the brain wasn't braining but got it at the end great explanation
Thanks Bhai. Its a tough question, but explained it very nicely.
Thank u for doing things for us even in ur busy days...❤
"Busy" are those People who disrespect others, People who respect are not Busy ❤
one of best video on yt
hello
If striver explains this question to a dead body and later asks him whether you understood or not. That dead body will yell from it's grave - "Understood Sir 💀☠"
Woah bro that's deep😅
UNDERSTOOD..........Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thanks bro
kya gajab video tha...
smaj aa gaya...
It is a Great question and explaination is just fantastic.
Thank you striver for the amazing content 🙇
Very good explanation, thank you for this video.
Brilliantly explained!!
I have also solved this but using another method:
Approach was to iterate one smaller array from 1 to n and applying binary search and insert the element into another vector using bs.
This was difficult to explain but great job Raj.
Best possible explanation !!
17:55 l1 > r2
Understood!! Amazing explanation
At 17:57 shouldn't it be l1 > r2?
Same thing i was thinkking
Even after knowing the solution this is the toughest question to code because of too many edge cases.
This man is genius
Super cute, at 24:06 not true not true like a very cute kid, Awesome Explanation :) Thank You
1 morning i would woke up and see striver had completed a2z series and i got my dream company.
Has the day come yet ?
Wow explanations. Big Thanks to Striver.
Its very helpful and clearly understand...
your explanation is awesome 😇😇. Finally i can rest in peace🙃
17:52 l1 is greater than r2 (correction)
At 18:02, you wrote l1 > r1, high will be eliminated. But, I think it should be l1 > r2.
Great lecture. Helped me a lot :)
Excellent explanation!!💌
great explanation buddy. Keep up the good work.
l1 should be greater than r2 right at 17:49 ?
Yup
One case that could have been discussed:
That is: Can there be a case where, l1 > r2 & l2 > r1. What to do in that case?
Answer: There cannot be such a case. This can be proved.
So let's assume l1 > r2 & l2 > r1 & try to reach to a contradictory statement.
So we know that r1 > l1 (Because array is sorted)
Therefore, r2
Hi bro . Recently i started to watch your array playlist. Today i watching this median problem . I clearly understood your logic at first time itself . I really amazed with your logical thinking . How could you come up with this logic . You are making me logical thinking and programming more interesting. I am started to learn all the concept . Now i am following logic which is already there. But the way you are approaching all the problem with different optimal solution, its very unpredictable. Please provide some tips how you have build your logic on each ptogram when you started your coding journey. That would help most of the freshers. Thank you!
Understood salute to striver🤓
Loved this approach❤
Maybe it will help :)
int mid2 = left - mid1; // left = how many elements i can pickup mid1 = how many i have picked up
Thank you so much broo for these series ☺️
Great explanation. Thank you ❤
very well described thankyou very much
@takeUforward, @30.01 generally in Binary search of array we consider left =0 and right=array.size()-1 correct?
But here why have you considered low =0 and high=n1 ( which is array size itself) not n1-1?
Yes because it means how many elements we take, either we can take 0 elements or we can take all which is n1
This is a little bit too much for me to digest, but at least I understood most of it.🙂
i thought of a different procedure first i will check if n1+n2 is odd or even and then proceed accordingly then i would use any vector and do a binary seach in it mid will act as a wall and if n1+n2 is odd there will be 2 walls one is mid and second is mid-1 then i would iterate between the elements of the other vector(where i have not applied the binary search) also i will count the one of elements on the left side of the walls and no of elemets on the right side of the walll then i will check for the first element of the other vector if that element is lesser than the a[low] then i will do left++ and move to the second element if it is greater than alow but lesser than wall1(basically mid-1) i will again do left++ if its greater than awall1 and smaller than awall2 then i will update the wall1 to that element and would do left++ (same can be done for right side) after iterating to all the elements in second vector i will compare the value of left and right
Thank you Striver sir 🥰
I did it using the approach of two sorted lists question and got 2ms solution. But this is better
beautifully explained!
Great Explanation!
Just one observation, while explaining solution you considered median to be r1/r2 value in case of odd total length, so left part doesn’t include median, but in coding part you have considered median to be l1/l2 which mean left part includes median. Got little confused with that.
Amazing Explanation! Thanks!
love your lectures
Great explaination..Thank you.💯
extordinary teaching bro
Happy teachers day !!
Understood 😊. You d best ❤
understood, perfect solution
this tutorial is awesome, thanks for this :)
CLEAN AS ALWAYS
18:43 determining how to pick the number of elements how did you comes up with this is this just observation skill ? or was there an intuition ? i dont think i would have seen such a pattern anyone knows the answer please help
Mind blowing video❤