Median of two Sorted Arrays of Different Sizes | Binary Search
Vložit
- čas přidán 28. 07. 2024
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Relevel Link: bit.ly/tufRelevel
Use "TAKEUFORWARD" coupon to get 10% discount.
Frontend info: drive.google.com/file/d/10aGL...
Business Dev info: drive.google.com/file/d/13Zje...
Backend Dev Info: drive.google.com/file/d/1RrzA...
---------------------------------------------------------------------------------------------------------------------------
Pr-Requisites: Binary Search
SDE sheet: bit.ly/takeUforward_SDE
✅Placement Series: • Let's give back to the...
✅Placement Series (Arrays, Sorting..): • C++ and Java |Brute-Be...
✅Hashing Playlist: • Two Sum Problem | Leet...
✅Greedy Playlist: • N meetings In One Room...
✅Recursion Playlist: • L8. Combination Sum | ...
✅Graph Playlist: • 3 MAJOR ANNOUNCEMENTS ...
✅Two Pointer Playlist: • 3 SUM | Brute | Better...
✅Binary Search Playlist: • Nth Root of a Number U...
✅LinkedList Playlist: • Reverse a Linked List ...
✅Advanced DS playlist: • Fenwick Tree Tutorial ...
✅Stack&Queue Playlist: • Implementation of Stac...
✅Greedy Algorithms: • N meetings In One Room...
Problem Link: leetcode.com/problems/median-...
C++/Java code: takeuforward.org/data-structu...
---------------------------------------------------------------------------------------------------------------------------
Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
---------------------------------------------------------------------------------------------------------------------------
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: bit.ly/tuftelegram (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
Problem Explanation and Naive Solution: 00:00
Relevel: 04:48
Efficient Solution: 06:38
#RelevelByUnacademy. #JobsForYou #striver #leetcode
Do write "understood" if you understood, motivates me :)
A common question, why take first smaller array, because the complexity of bs is search space, so the smaller the search space, smaller the complexity. You can take the larger array, but the search space will be bigger.
Insta: instagram.com/striver_79/
Telegram: bit.ly/tuftelegram
Waiting for tree series like graph's one
Sir
you really a life saver for us ❤️.
Thank you for your lectures. 🥺🥺❤️
*VERY IMPORTANT*
Bhaiya!!! when you solved this problem for the first time... were you able to think of the most optimal solution by yourself?? or you also read about the problem and watched some videos?? because many of the times we are able to solve the problem but not able to fully optimise it... sometimes i feel really demotivated when i am not able to do so
Sir can you explain why in the size of odd sized subarray we took cut2 at (n1+n2+1)/2-cut1 and not at (n1+n2)/2 -cut1. What's the problem with (n1+n2)/2
Is this the optimal solution
In the middle of the video I went to other channels (as it was looking a bit difficult) but came back again and let me tell you this is one of the BEST explanation available for this problem.
Once again...Thanks a lot Striver !!!
Thankyou for the trust .. I make sure the video is re-recorded if it looks tougher on the first recording. Please keep sharing.. 😌
@@takeUforward
Yeah, sure.
I really appreciate your help to CS community.
Same happened with me but striver made it
Lol. I am in that phase of going to other channels. Will be back in an hour.
@@anshulkumar7871 me too
Here's the intuition that helped me understand this. In this problem, we are searching for the "correct partition" in an array, such that,
1. Number of elements in the merged array is (m+n) // 2
2. All the elements in the left partition of both the arrays are lesser than or equal to all the elements in the right partition of both the arrays
3. If ALeft > BRight --- shrink the partition
4. If BLeft > ARight --- increase the partition
How do we know we can apply Binary search?
- We have a rule which can tell us if we should move to the right or to the left in the solution space
Here binary search can be run on any of the arrays, but we choose to run on the smaller one as it's more efficient.
Must say the way this has been explained so simply is commendable! A binary search over where to partition both the sorted array so as to form the first half of the merged sorted array.
@Striver, you nailed it man. Words would be less to appreciate your effort. The way you were explaining was like building block by block and totally intuitive. After watching the explanation, I was able to code it without any issues. Thank you for this. Keep going forward. You are doing a great job by helping other fellow programmers.
Hey could you explain that why taking first array to be smaller gives answer and not other way round?
if we remove
if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2, nums1);
from code , it fails..why??
Hi@@shwetanksingh5208 . I also did the same mistake by not giving the attention to this if condition. Our goal while solving the problem is to reduce the overall time complexity of the solution. We know that the time complexity of this approach is O(log n), when n is the size of the smaller array. If you choose the larger array, the time complexity will be some bit larger. @Striver has already, pinned this doubt in the comments section.
@@codingwithsmallsteps2878 You don't get TLE when you remove this condition, you get out of bound issue.....and the reason for it I was asking?
Hey since u understood it ,can u tell me why we took high=n1 and not (n1-1). Because the last index of the vector is (n1-1). Putting (n1-1) throws error immediately. Why is it so?
@@shwetanksingh5208 shwetank, if u want more clarity on this issue then i recommend u watching "how to find kth smallest element in two sorted arrays of different sizes by the same channel. But i will tell u here why is it
So,lets say we want to work on the larger array rather than the shorter array. Now, m->size of larger array,n->size of smaller array. So,the half of it will be (m+n)/2. Now,if we will see if low=0 and high=n is possible or not. lets take an eg: take larger array on which we are operating ,its size be 5 and smaller array's size be 3. so we need to put half of the total elements which is (5+3)/2 = 4 . So,if low=0;that means our larger array is empty and we have put all the 4 elements in the smaller array of size 3 which is not possible if low=0. therefore the minimum value of low cannot be zero. it will be (4-3) i.e in general it will be (m+n)/2 - n. Similarly, can high be 'm'? let us see. so if high =m, in this case it is 5. so it means that in that case the larger array is full but we only have 4 elements to fill the larger array. How can we fill 5 spaces with 4 elements? So it is not possible. we can fill the 4 elememts upto 4 places only in the maximum case. We cannot fill it upto 5th place. so in maximum case, the maximum value of high =4 i.e. in general the max value of high=(m+n)/2 and not m.
so overall if you remove the 'if' condition on the first line , you have to separately write the condition low= (m+n)/2 - n and high = (m+n)/2 when you are considering the larger array. if you are considering the smaller array low and high will be 0 and m respectively. you can observe it.
Problem solving is surely a skill. But explaining the solution in simple way like this is a blessing. Great video!
Why we take high = n1 and not n1 - 1 because we are taking low = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
I really struggled to understand this problem, but your explanation made it much easier, nice work!
Thanks man , you really know how to teach ..i understood it so well that i was able to code this in python with great ease,thanks alot
I have thought of the other solution based on what we did in median of two sorted arrays approach. We can take the low as min(arr1[0],arr2[0]) and high max(arr1[arr1.size()-1],arr2[arr2.size()-1]) and go on by solving the way we did in the median of two sorted arrays. I think that will also have the time complexity as O(log(max)*log(n)*log(m))
Here is actually a semi-formal explanation of why the complexity is O(log n) where n is the size of the smallest array. What you are actually looking for is a number k, such that partitioning at the index i such that A[i] = k gives k as the median. Sure, you don't know what k is. BUT, when picking an index i to find k, you can tell in a single operation: 1) Is A[i] the k we were looking for? and 2) If it is not, I need to search in either the left sub-part or the right sub-part of the array. In that sense, the search is a standard binary search. Except instead of A[i] == the number were looking for, for 1) it is left1
Why we take high = n1 and not n1 - 1 because we are taking low = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
understood, l1 < r2 and l2 < r1 is the one key concept, another is moving the med of only smaller array,
After watching about 10-12 videos on this...I finally found your video...nd ur explanation is just awesome. It's at another level. May God bless you.thank you striver ❤️❤️ ..keep teaching us
Why watch 10-12 videos when tuf has a video on it 🙈
explain that why taking first array to be smaller gives answer and not other way round?
explain this code bro
if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2, nums1);
Why we take high = n1 and not n1 - 1 because we are taking low = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
ur explanation is ###1 .. havent done algos for 5 years so very rusty and glad I found your channel thanks!
Maja aa gaya! I literally wrote 7 pages of explanation myself after getting the complete thought process of the question. Thanks man!!
Share with us also bro...It will help me.
Kuch jayada nahi bol diya🤣
but how will you explain this 7 pages to the interviewer in less than 10 mins
7 page jitna kuch samajhne ke liye nahi hai 🙄🙄🙄🙄
@@sleepypanda7172 bhai dsa aisa hi hota hai, kuch concept wagera nahi hai, bas question rat ke chale jaao, ho jaayega, baaki ye sab bakwaas kisi ke kaam aana nahi kabhi
Brilliantly explained. Can't thank you enough ❤️
I understand the whole code without seeing the code. You're a genius man ,no one in the world will beat your programming logic.❤❤❤
i will try
100% best explanation I've seen, especially including the formula explanations and how they relate to what you're doing, and the visual changes that show the effects of changing values.
Why we take high = n1 and not n1 - 1 because we are taking low = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?
I've done this problem on leetcode by seeing the discussion part but not able to understand the intuition behind the code.
Thanks striver for such an easy explanation of the intuition now I dont have to memorize the code.
Hey,since you understood so could you explain that why taking first array to be smaller gives answer and not other way round?
if we remove
if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2, nums1);
from code , it fails..why??
@@shwetanksingh5208 same bro .........i didn't understand that point........
@@ABDULAZEESBEC going othwr way round won't give TLE as they are saying ("smaller search space") rathet it will throw out of bound error which no one has explained here
Hey, you can take it in any order unless , you go out of bounds . Meaning, when you have to move the cuts , you can pick an excess number of elements only from the array that have greater number of elements. If you don't know which array has larger elements you have to check this each time you need to move the cut, that is why at the start itself we keep the order, being first array is smaller and second is larger or vice versa.
Really good explanation. Very clear and concise explaining every concept used in this problem. Being grateful after watching your video. Thanks a lot folk.
This is the best video I've found for this problem! You are the man!
Great explanation and great energy/enthusiasm! I appreciate your time making this video!
Agreed! The rest of the places they just hand out the mathematical formulas :(
explain that why taking first array to be smaller gives answer and not other way round?
explain this code bro
if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2, nums1);
Why we have to do binary search on smaller array?why you change num1 and num2 on first line?
My correct code:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m = nums1.size();
int n = nums2.size();
// we will calculate the contribution size of the smaller vector
if(m > n)
return findMedianSortedArrays(nums2, nums1);
int low=0,high=m,medianPos=((m+n)+1)/2;
while(low>1;
int cut2 = medianPos - cut1;
int l1 = (cut1 == 0)? INT_MIN:nums1[cut1-1];
int l2 = (cut2 == 0)? INT_MIN:nums2[cut2-1];
int r1 = (cut1 == m)? INT_MAX:nums1[cut1];
int r2 = (cut2 == n)? INT_MAX:nums2[cut2];
if(l1
beautifully explained Raj, thanks.
I had a doubt, during coding rounds, can we use STL methods for say binary_search, heaps etc, or do we need to write our own implementation?
can we do binary search on the array with large size instead of array with minimum size?
why cut1 is only performed on smaller array other than making a small search space for binaryb search?
Do we need to put extra conditions like if any of the array size is zero or both of them are of size 0?
Best explanation ever.There is no one on the entire youtube who can explain this question better than you! Just a mistake that at 18:25 secs it must be 0+3/2 and then we will get index 1... I really got confused here for a bit.! May be I am wrong.
Amazing explanation striver bhaiya. I can't thank you enough for whatever you are doing. Thanks for making DSA questions explanations very easy. Thank you :)
Not sure if I'd get the intuition if someone else explained me this 🔥🔥🔥 your explanation is just awesome beyond the words could ever describe
was struggling to understand it from past 2 days, but found this explanation!!! Amazing man hats off for such wonderful explanation
Hello, i did not understood the part where you are taking n1+n2+1, why +1? and how its working for both even and odd cases. Question 2: in basic binary search we are taking high as array size -1 but here you have taken array size why this is needed?
Liked the way you worked backward from the result and framed concept from it. Keep it up
I truly appreciate you striver for explaining us with this much patience♥
Thanku for being our support
Excellent one of the best logic and easily understandable .Thnk u so much
awesome explanation, makes a hard problem really simple with this explanation, thanks a lot!!!
What an amazing explanation bhaiya every minute in this video is "Ohh haa smje" wala moment discovering new perspective of looking Qs.
I strongly wish to have a explanation skills like you so that in Interview also Interviewer says WooW
why do the binary search on the most shorted array?
OP
Firstly I stop to watch in the middle because of toughness (critical) but when I watched it again in one go ... It really help me to understand the problem...
Thanks Man for this beautiful explanation 😊
I went through so many videos for an explanation of this. Your explanation is the best.
Amazing explanation and understood it very clearly! Keep putting out videos like this
I cant thank you enough Striver 🙏🙏
Your contribution is phenominal!
why to choose the smaller array for doing the binary search , someone please explain
because there is less elements in smaller array to apply binary search so more optimize..
So the time complexity which u said O(n) is for the best case scenario right? Wouldn't it increase for the worst case?
Why do you always obtain mid by right shift as (lo + hi) >> 1 instead of simply (lo + hi) / 2 ?
Bit operations are faster
Instead do l+ (h-l)/2 to avoid overflow in some questions
THANKS FOR THIS AWESOME EXPLANATION.
UNDERSTOOD ❤❤❤❤
Hi ,
If we write without line 4 of a smaller array why doesn't the code work?
I tried without using it but it didn't work!!
Can someone help?
very much detailed explanation , was able to understand in first go and code it myself , though at first , I got TLE , but after that i optimized it
Why is it necessary to binary search on the minimum length array??
That is the most amazing explanation I have ever saw for this problem :) thanks
In your example, 12 !
Smart! Because it’s more efficient to pick the middle element for large quantities of elements, binary search.
Understood. such an easy explanation of this complex solution. You just created one more fan ❤
Hi Bro, Could you please explain why we are doing binary search on smaller array?
haven't watched the whole video but the code at last was most readable and easy to grab...no confusion any more..thank you
Excellent Explanation!!
Thanks for keeping us motivated.
Well explained!! Only video I found with such a clear explanation!!
After your explanation even hard problem sounded in my reach XD. Very well explained.
one other solution if you're allowed extra space is you can use max heap for left half and min heap for right half
if i am not wrong this question is a variation of the heap one??
@takeUforward why are we considering shortest nums array as the first one. Any particular reason for doing that or to make complexity O(log(min(m, n)))?
Can anyone explain why we need smaller size array to perform binary search
I have a ques why U have added the first line : if nums2. size() < nums1. size()........
if we remove that line that gives a runtime error Please elaborate
Understood! Such an excellent explanation as always, thank you very much!!
This is work for the same sizes as well, but is there a way to optimise this for same sizes of array?
bht hi shaandaar sir. solution dkh ke laga nhi tha ki samjh me aa jaayega. itna bada explanation notes first time bnaya alag hi maje aa rhe h.
thanks man
This proves how in depth knowledge you have, just god level teaching, thanks a lot man.
please someone , what does this do
(int cut2 = (n1+n2+1)/2 - cut1);
Thank you bhaiya for the awesome efforts ! Even we will inculcate this seva bhav in ourself and give back to the community and help you! after we crack our placements and all!
pls tell me if we use (n1+n2)/2 we just have to change median as min(r1,r2) t doesnot create an differrence right?
Hi, Can you help me understand how its O(min(log m, log n)) and not O(n) ? let say we have to traverse from half of first arr to its end and further down the 2nd array so we are definitely traveling n/2 of length of each arrays and O(n/2) is o(n)
You would be traveling that length but you wouldn't be moving one place at a time, instead you would go to 3n/4, 7n/8 and so on; this is log(n/2) - which is O(logn) - rather than O(n); by one place at a time I mean n/2, n/2+1, n/2+2, n/2+3...
This one's an awesome problem!
Understood!
crystal clear solution !!!
Thank you so much striver😃😃!!
Do post amazing contents .
Best video on this question on youtube - thanks so much. Couldn't understand it until I watched this
Why do we have to keep the array bigger in size as the second array only (nums2 in the code) , why can't we generalise it?
Because to refuce the search space, thereby reducing complexity
Bhaiya I submitted Brute Force approach without using Binary Search and Got AC . Like you mentioned in video . In interview can we do this directly . Beacuse if this question comes in form of a story then Mind automatically goes for Brute Force
understood and your explaination just awesome thanks a lot for this awesome content I watch this video twice to clear my concept but now its totally clear
Best ever Explanation on CZcams...........
Thank you very much bro you made my life very much easier by seeing these videos. It's been really helping a lot. Keep it up bro!!
@Striver, the way how you did the dry run is super simple for such a hard problem. No words and everything is clear at the first go. Thanks for your time and efforts.
That was an amazing explanation, thanks for such an detailed video☺
Thank you so much for such amazing videos on searching🙏🙏
Great explanation. Could you please share the software/hardware that you use for your videos?
totally understood, and appreciate your teaching skills. it's amazing🔥
Nice explanation your videos are really good...please keep on making such videos.
bhaiya why we take first array always of smaller or equal size then of second array .
is this just for make time complexity less or due to some edge cases.
plzz answere .
the way you explain is just like water.thank you bhaiya
**VERY IMPORTANT**
Bhaiya!!! when you solved this problem for the first time... were you able to think of the most optimal solution by yourself?? or you also read about the problem and watched some videos?? because many of the times we are able to solve the problem but not able to fully optimise it... sometimes i feel really demotivated when i am not able to do so
Nah I could not.. read some leetcode discuss answers, then did..
P.S: back in 2019 I did when i was preping for interviews..
@@takeUforward Thanks for being genuine.
@@takeUforward Thanks man, keeps us motivated enough to know that we are not the only ones struggling with hard questions. Thanks again for the great explanation.
Same problem with me
@@takeUforward Loving your honest reply, great!!
What is time complexity of the statement n1 = nums1.size() ?
Is it O(n) or O(1)
Wonderful explanation bhaiyaa..... Likes a lot !!!!
Will the code run for the input :
nums1 = {-41, -33, -24, -21, -20, 27, 48} and nums2 = {-9} ?
Correct answer should be -20.5 but using this algo its 30.0???...
@take U forward I have a doubt bro like why we are not updating/shifting cut1 & cut2 except that we are updating low and high pointers & then calculating cut1 & cut2, what if we update cut1 & cut2 when comparing without updating low and high pointers ?
Because we know cut1 will be in left, hence acc to binary search we reduce the search space to figure out the between
@@takeUforward ok so just bcz we are using binary search we are updating low and high pointers to find the mid basically.
But as we also know that from 0 to all elements maybe needed we can just shift our cut1 from taking all elements to none linearly to satisfy the condition.
Am I right?
@@ash_79 yeah
@@takeUforward understood brother. Thank you 😊
I couldn't get the point why we are selecting smaller array. Can anyone explain
Such a great explanation with proper flow of logic
Holy shit....did he just explain this mind boggling problem so simply. Salute sirji.
Sir why you didn't took cases of total number of 1 and 5 elements for left half from array 1?
Nice Explanation , superb . I have became fan of your's !!
Hamre dronacharya ❤
Lil
Tb tumhe bhi eklavya banna padega.
@@willturner3440 haha
Why we are doing binary search on always smaller size array ?
I'm like numb after watching this.....you have been always the best 🌟 keep shining and keep uploading :-)
Bhai you explain so well, really nice communication skill man.
Ah.!What an excellent explanation.!!!
Thanks..
this code will fail for these two arrays
[1,2,3,5,6]
[4]
correct me if im wrong.
Hey great videos but I loved the representation which you followed before in digital sketch board . Can you please go back to that?