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.
@@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.
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 💀☠"
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 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 :)
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)))
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.
@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?
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.
Pseudo code is mostly important in hard level questions and you droped it from this video irritating !! I hope further videos of playlist is with proper explanation and psedo code
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
From A2Z sheet i must say I've watched every video and found the approach best but unfortunately i was not able to consider this as the easy/optimal approach as in previous questions approach striver used to deliver us.
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
How did we get the thought of using mid1 and mid2 to get the values of l1,l2 and r1,r2 ? Like how do we think that mid1 will be pointing to 2nd index of arr1[ ] and we can use it to determine the values of l1,l2 and r1,r2... Please clear the doubt @takeUforward
Why is high initialised to n1 and not n1-1. Isn't it supposed to be the last index of the smaller size array. Usually we initialise low to 0 and high to last index which is n-1. But here it is initialised to n. Why so?
Understood. Low and High are referring to number of elements from smaller size array. The names are a bit confusing since usually we have been referring low, high and mid to array indices all along in the course. Given 2 arrays A and B, We basically need to create 2 partitions, left and right such that left contains all elements less than median value and right contains all elements greater than median value. For programmatic purposes, we keep the median value in left partition itself, when number of elements are odd. When number of elements are even, we equally divide between 2 partitions. If our smaller array has 10 elements and bigger one has 20 elements, then we need to create left and right partitions with each having 15 elements. We can include 0(minACount, called low in the video) to 10(maxACount, called high in the video) elements of A in left partition. We first try with 5(candidateACount, called mid1 in video) elements of A and 10(candidateBCount, called mid2 in video) elements of B first. If this does not produce result, we check if 5 elements from A are too many or too few. - If it is too many we need to reduce the elements from A in left partition. So we now have a choice of keeping 0(minACount) to 4(new maxACount) elements from A. We then try with 2(new candidateACount) elements from A and rest from B. And so on. - If it is too few we need to increase the elements from A in left partition. Since 5 was too few, we need to keep more than 5. So we now have a choice of keeping 6(new minACount) to 10(maxACount) elements from A. We then try with 8(new candidateACount) elements from A and rest from B. And so on. Ultimately we will be able to find the right partitions. Also we can refer to l1, l2, r1, r2 with the names aRightMostInLeftPartition, bRightMostInLeftPartition, aLeftMostInRightPartition, bLeftMostInRightPartition respectively. Just replacing these names in the code from the video was able to make the understanding much easier for me. Hope it helps others. public int median(int[] a, int[] b) { int sa = a.length; int sb = b.length; int total = sa + sb; if(sa > sb) { return median(b, a); } int partitionCount = (int)Math.ceil((double)total/2); int minACount = 0, maxACount = sa; while(minACount = 0 ? a[candidateACount-1] : Integer.MIN_VALUE; int bRightMostInLeftPartition = candidateBCount - 1 >= 0 ? b[candidateBCount-1] : Integer.MIN_VALUE; int aLeftMostInRightPartition = candidateACount < sa ? a[candidateACount]: Integer.MAX_VALUE; int bLeftMostInRightPartition = candidateBCount < sb ? b[candidateBCount]: Integer.MAX_VALUE; if(aRightMostInLeftPartition aLeftMostInRightPartition) { minACount = candidateACount + 1; } } return -1; }
I think the time complexity is not the only reason why you should do a binary search on an array whose size is smaller. If you will do a binary search on the array with a bigger size, then you will not be able to construct the first array (left partition) to make two arrays asymmetrical
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
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.
This is a very nice video and possibly one of the best explanations. I just have one suggestion - because you're teaching this online, if you could speak softly, I am sure people would appreciate it. Right now, it seems like you're shouting. I wish you the best, don't take this comment harshly
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 !
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.
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!
because taking high as n1-1 would not cover all case.......for eg. In array of size 4 if we take high as n1-1; it would result mid in 0+3/2=1; but ideally if our answer is 2 we would simply lose that!!! hope it helps!!
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???
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
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😅
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
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.
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 :)
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)))
At 17:57 shouldn't it be l1 > r2?
Same thing i was thinkking
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.
@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
i tried to do it in zero-based. if e.g nums1=[1,3] nums2 = [2].
arr1Left = 2,
arr1Right = inf,
arr2Left = -inf,
arr2Right = 1.
arr1Left
Watched both videos twice ,all 3 approaches are crystal clear now,thank you!
Waiting for this one for a long time no one explained this problem this well , Thank you.
If i hadn't checked this video there is no way i would be able to think of this solution in interview
Thanks...
That swapping of the inputs and >>1 steps are 🔥 🔥
bit manupulation and swapping is to low so yeah it improves time mostly
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.
1 morning i would woke up and see striver had completed a2z series and i got my dream company.
This is one of the bestest explanations I have come across. Totally cleared my concept. Thanks a lot sir !
i doubt is it even psbl coming up with this soln in a real interview? my brain just blew..this is a crackhead problem
Pseudo code is mostly important in hard level questions and you droped it from this video
irritating !!
I hope further videos of playlist is with proper explanation and psedo code
l1 should be greater than r2 right at 17:49 ?
Yup
The idea clicked the moment he said how many elemts to pick from both the arrays.
Started coding it and damn it was tough to code it (edge cases 💀)
Isn't intuitive at all.Must be done beforehand.
why you taken 6 in limit , we have to take only five value???
Same doubt, high = n1-1 kyu nhi hai?
Bro i couldn't understand the need of that dummy return statement
The king of coding community 👑
This is a little bit too much for me to digest, but at least I understood most of it.🙂
why can't we take this case to eliminate right?
if(l1 > r2 || l2 > r1) high = mid - 1;
I did it using the approach of two sorted lists question and got 2ms solution. But this is better
Maybe it will help :)
int mid2 = left - mid1; // left = how many elements i can pickup mid1 = how many i have picked up
UNDERSTOOD..........Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
After watching so many videos i actually the found the gem which resolved my all the doubts in such a nice and simple way.
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
17:55 l1 > r2
Amazing, how you observe so minutely :) Bhai Hat's Off .
At [17:23], you're picking 4 elements from the "Top" (not "Left"). Slips of the tongue make the matter very difficult to follow.
From A2Z sheet i must say I've watched every video and found the approach best but unfortunately i was not able to consider this as the easy/optimal approach as in previous questions approach striver used to deliver us.
Understood
Understood! Super amazing explanation as always thank you very very much for your effort!!
At first the brain wasn't braining but got it at the end great explanation
Crystal clear explanation. Explained your heart out. Thank you :)
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
17:52 l1 is greater than r2 (correction)
17:50 Its l1 > r2 :)
Hats off to you Broh... THANKS A MILLION 💙💙💙
Really wonderful approach and explanation
awesome explanation
@17.50 condition should be --- (l1 > r2) instead of (l1 > r1)
I give gurrante you are what I am saying I don't understand 😅 it's your mistake
Can we do max of left shoulder be less than min of right for a valid symmetry
How did we get the thought of using mid1 and mid2 to get the values of l1,l2 and r1,r2 ? Like how do we think that mid1 will be pointing to 2nd index of arr1[ ] and we can use it to determine the values of l1,l2 and r1,r2... Please clear the doubt @takeUforward
yea even im having the same question, plus, why is mid2 pointing to the 2nd array?
problem is okayish not too hard,but takes time to understand indexing.
Understood
understood
Why is high initialised to n1 and not n1-1. Isn't it supposed to be the last index of the smaller size array. Usually we initialise low to 0 and high to last index which is n-1. But here it is initialised to n. Why so?
Understood. Low and High are referring to number of elements from smaller size array. The names are a bit confusing since usually we have been referring low, high and mid to array indices all along in the course.
Given 2 arrays A and B, We basically need to create 2 partitions, left and right such that left contains all elements less than median value and right contains all elements greater than median value. For programmatic purposes, we keep the median value in left partition itself, when number of elements are odd. When number of elements are even, we equally divide between 2 partitions.
If our smaller array has 10 elements and bigger one has 20 elements, then we need to create left and right partitions with each having 15 elements.
We can include 0(minACount, called low in the video) to 10(maxACount, called high in the video) elements of A in left partition.
We first try with 5(candidateACount, called mid1 in video) elements of A and 10(candidateBCount, called mid2 in video) elements of B first. If this does not produce result, we check if 5 elements from A are too many or too few.
- If it is too many we need to reduce the elements from A in left partition. So we now have a choice of keeping 0(minACount) to 4(new maxACount) elements from A. We then try with 2(new candidateACount) elements from A and rest from B. And so on.
- If it is too few we need to increase the elements from A in left partition. Since 5 was too few, we need to keep more than 5. So we now have a choice of keeping 6(new minACount) to 10(maxACount) elements from A. We then try with 8(new candidateACount) elements from A and rest from B. And so on.
Ultimately we will be able to find the right partitions.
Also we can refer to l1, l2, r1, r2 with the names aRightMostInLeftPartition, bRightMostInLeftPartition, aLeftMostInRightPartition, bLeftMostInRightPartition respectively. Just replacing these names in the code from the video was able to make the understanding much easier for me.
Hope it helps others.
public int median(int[] a, int[] b) {
int sa = a.length;
int sb = b.length;
int total = sa + sb;
if(sa > sb) {
return median(b, a);
}
int partitionCount = (int)Math.ceil((double)total/2);
int minACount = 0, maxACount = sa;
while(minACount = 0 ? a[candidateACount-1] : Integer.MIN_VALUE;
int bRightMostInLeftPartition = candidateBCount - 1 >= 0 ? b[candidateBCount-1] : Integer.MIN_VALUE;
int aLeftMostInRightPartition = candidateACount < sa ? a[candidateACount]: Integer.MAX_VALUE;
int bLeftMostInRightPartition = candidateBCount < sb ? b[candidateBCount]: Integer.MAX_VALUE;
if(aRightMostInLeftPartition aLeftMostInRightPartition) {
minACount = candidateACount + 1;
}
}
return -1;
}
Best video explanation of this problem on the whole internet.
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 ❤
Why cant i run binary search on answer range as smallest and greatest value
TOP notch explanation striver. I saw both videos. Understood completerly. Thank you.
I think the time complexity is not the only reason why you should do a binary search on an array whose size is smaller. If you will do a binary search on the array with a bigger size, then you will not be able to construct the first array (left partition) to make two arrays asymmetrical
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
this logic seems to fail for A : [ -43, -25, -18, -15, -10, 9, 39, 40 ]
B : [ -2 ] any idea why ??
Brother It does run fine on this as well 👍🏻
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.
I didn't get the reasoning behind adding 1 while initialising left (int left = (n1 + n2 + 1) / 2;) . Can someone help me with this?
(2+3)/2=2........(2+3)+1/2=3... as adding 1 would cover more cases so that why he added extra 1
but i havee got time limit exceeding even in small test cases why?
Striver >>>>> EZ snippet
What a energy !
Thank you striver for amazing content 🙇
thanks bro
kya gajab video tha...
smaj aa gaya...
This is a very nice video and possibly one of the best explanations.
I just have one suggestion - because you're teaching this online, if you could speak softly, I am sure people would appreciate it. Right now, it seems like you're shouting. I wish you the best, don't take this comment harshly
why did you reupload? we already have the same lecture
Its different, we are going to patternwise learning.
@@takeUforward please upload videos of next playlist as well ,eagerly waiting for thar
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 !
Its very helpful and clearly understand...
Mind Blowing Solution approach
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.
Hey, Striver this is illegal solution 😂😂
Hi Striver, It was a great explanation. Thank you !!
Can you please explain that, why are taking first vector is always smaller?
how do people come up with these kind of solutions
can i slove with matrix median technique
Brilliantly explained!!
I shocked at the end of video after seeing the way you explained this complex optimal solution!!!!
Thanks a lot!❤🔥💥❤💯
Understood!! Amazing explanation
brilliant explanation. even hard topics seem easy when you explain them.
i think so to find out left we can use (n1+n2)/2 and change median as min(r1,r2) nothing much difference right??
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!
Bhaiya which topic will come next ?.....what are upcoming plans
Can someone please share the program for this
brilliant explanation, this problem is not only hard to do but also hard to explain
Finally I can rest in peace
Super cute, at 24:06 not true not true like a very cute kid, Awesome Explanation :) Thank You
Thanku for making optimal vedio separately for this problem 🥲❣️🙌🏻
at 29:52 why do we take high as n1 and not n1-1 ? Someone pls explain fast.
because taking high as n1-1 would not cover all case.......for eg. In array of size 4 if we take high as n1-1; it would result mid in 0+3/2=1; but ideally if our answer is 2 we would simply lose that!!! hope it helps!!
17:41
Best video. I watched twice and understood great effort and awesome solution 🔥🔥
Neetcode is better for this question.
Iske expression dekhke hi flow bigad jata hai or iski english , his accent came from whole different dimension
Thanks Bhai. Its a tough question, but explained it very nicely.
This is a great approach, no way I could come up with this in an interview...
nice
Khatarnak but bhot kuch seekha !
yeah bro i did this the first time i saw it. took ~ 15 minutes
im also a billionaire btw