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
*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
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 !!!
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.
@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.
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.
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?
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.
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
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?
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?
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];
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?
@@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
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??
@@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.
The discussion focuses on finding the median of two sorted arrays using binary search. It explains the naive merging method and introduces an optimized approach that maintains a counter to track relevant elements. The video also highlights the importance of checking conditions for valid partitions and provides a C++ code implementation with time complexity analysis. Highlights: 00:05 Finding the median of two sorted arrays is a challenging problem that requires understanding the merging process. Solutions can vary from naive methods to optimized approaches, impacting efficiency significantly. -The median is defined differently based on the length of the merged array, which can be even or odd. Knowing how to compute it correctly is crucial for accurate results. -A naive solution involves merging the two arrays and then finding the median, which has a time complexity of O(n1 + n2). This method, while simple, is not optimal. -An optimized approach reduces the space complexity to O(1) by only tracking necessary elements instead of merging entire arrays. This method is more efficient and effective for larger datasets. 06:01 The discussion focuses on an effective strategy for solving problems using optimized methods, specifically emphasizing the use of binary search for sorted arrays. This approach can help in decision-making and problem-solving during interviews. -Utilizing coupon codes can significantly reduce costs, making it easier for individuals to access resources they need for career advancement. Consider using codes like 'take you forward' for discounts. -Preparation for interviews is crucial, and utilizing algorithms like binary search can impress interviewers by showcasing efficient problem-solving skills. Understanding optimized solutions can set candidates apart. -The ability to validate solutions is essential in problem-solving. Ensuring that selected elements from arrays meet specific conditions is a key step in achieving correct outcomes. 12:03 Binary search is a powerful algorithm for finding the median of two sorted arrays. It requires checking the validity of partitions to ensure the correct median is identified. -Understanding how to find the median involves calculating the maximum of the left half and the minimum of the right half. This is crucial for determining the median correctly. -The validity of partitions is essential. The conditions state that elements of the left half must be smaller than those in the right half. -Adjusting partitions can be done based on comparisons. If conditions are not met, shifting left or right will help in forming a valid partition. 18:06 The process of finding the median from two sorted arrays involves determining the correct partitions, referred to as cut one and cut two. By ensuring each partition meets specific conditions, the median can be accurately calculated. -Understanding the concept of partitions is crucial to finding the median. Each cut must represent a valid division of the two arrays for accurate calculations. -Binary search plays a significant role in adjusting the partitions. By moving left or right through the arrays, the correct cuts can be established to determine the median. -Comparing the maximum of the left elements with the minimum of the right elements is key. This ensures that the partitions are valid and helps in finding the median. 24:09 Understanding the process of finding the median of two sorted arrays involves partitioning and validating segments of the arrays based on their lengths. Proper handling of edge cases ensures accurate results in median calculations. -The significance of edge cases in median calculations is emphasized, particularly when no elements are selected from one array. This ensures proper assignment of minimal or maximal values. -The algorithm's adaptation for both even and odd total lengths of the arrays is crucial. Different formulas apply for calculating the median based on the length's parity. -The implementation of binary search aids in efficiently determining the partitions of the arrays. This approach simplifies the process of finding the correct cuts for median calculation. 30:00 The explanation covers how to find the median of two sorted arrays using binary search. It emphasizes that the arrays must be sorted to ensure a valid partition for the algorithm to work. -The process involves moving pointers to create a valid partition, ensuring the algorithm adheres to the constraints of the given sorted arrays. This is crucial for accurate results. -Time complexity is discussed as log base 2 of the minimal length between the two arrays, indicating efficient performance during the search process. -Space complexity remains constant at O(1), showing that the algorithm does not require additional space, further contributing to its efficiency in computation.
**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
@@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.
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!
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);
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.
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))
@@DustZone033 if you're asking for the geeksforgeeks one then yes, I still recommend taking it. Most of the times, Sandeep Jain provide better explanation than any video on UA-cam. And also that dsa self-paced course has everything you need. All topics are covered with all approaches for every problem. And doubt solving facility is also there
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
Really good explanation. Very clear and concise explaining every concept used in this problem. Being grateful after watching your video. Thanks a lot folk.
I think the efficient solution works considering that elements in nums1 is less than elements in nums2. Also the case when any one of the arrays is empty needs to be handled separately.
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??
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?
Honestly mera faat gaya first time dekh kar... so I tried to skip and tried to find something better... But on watching more vid.... I realized that the video i paused and left was the best explaination. Thnx Striver....
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
@Striver,I have a doubt. Just assume the size of the first array is 6 and second one is 4(total 10). so we have to take 5 elements from both the array. but here high is initialized to n1(the size of arr1) in this case which is 6. how can we take 6 elements from arr1? 🤔..anyone knows abt this, pls comment.
I think it won't be possible bro even for him ... he would have to go in a sequential manner! till then you could check out Kartik Arora's youtube channel for dp ... I have heard from many students that it is good...you could definitely check that out..! otherwise online resources are there only!
If you need to survive on someone else to make you successful you wouldn't be successful in the first place, these videos are good but not having dp videos should not be the reason for your failure there are many good resources on the web. just a food for thought!
I swear, if an interviewer asked me for the binary search method of this problem I'd be tempted to slap them. The binary search method is beyond unintuitive, like if you never seen this problem, it is very very very unlikely you would come up with this on your own, especially in 45min
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 😊
@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.
@@takeUforward No I tried it, it can give you an ArrayIndexOutOfBounds error if you use the larger array for binary search. Try this: Array 1 : [1,2,3] Array 2 : []
Also if u dnt perform binary search on shorter array code fails for a case like : {0} {} . Dry run and try to perform binary search on the larger array u will understand.
@@takeUforward yes bhaiya bt in the code there ws no such condition that if an array is empty calculate directly(so it becomes an edge case) .... That's why the code gives error in the above test case if we do not do binary search on the smaller array always (i.e. if we omit the first if from the code).....so doing Binary search on the smaller array is important. I ran this test case on leetcode without the above if part and with the above if part to confirm. Btw thanks for the great work that u do......
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
@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't we do this question by simple binary search......... consider two variables low = min(a[0],b[0]), high = max(a[n-1],b[m-1]), we know that our answer must lie in this range. Take the mid element and apply lower_bound to find like how many elements are less than or equal to our mid. If count == median index which we can calculate. Then our answer must be max(last elements less than equal to mid in both arrays), else if count is less, than we can shift our low to mid+1 or if greater than shift our high to mid-1.
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
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 :)
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!
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 .
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???...
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?
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
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.
@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?
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
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.
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?
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
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?
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
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?
understood, l1 < r2 and l2 < r1 is the one key concept, another is moving the med of only smaller array,
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
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.
haven't watched the whole video but the code at last was most readable and easy to grab...no confusion any more..thank you
ur explanation is ###1 .. havent done algos for 5 years so very rusty and glad I found your channel thanks!
The discussion focuses on finding the median of two sorted arrays using binary search. It explains the naive merging method and introduces an optimized approach that maintains a counter to track relevant elements. The video also highlights the importance of checking conditions for valid partitions and provides a C++ code implementation with time complexity analysis.
Highlights:
00:05 Finding the median of two sorted arrays is a challenging problem that requires understanding the merging process. Solutions can vary from naive methods to optimized approaches, impacting efficiency significantly.
-The median is defined differently based on the length of the merged array, which can be even or odd. Knowing how to compute it correctly is crucial for accurate results.
-A naive solution involves merging the two arrays and then finding the median, which has a time complexity of O(n1 + n2). This method, while simple, is not optimal.
-An optimized approach reduces the space complexity to O(1) by only tracking necessary elements instead of merging entire arrays. This method is more efficient and effective for larger datasets.
06:01 The discussion focuses on an effective strategy for solving problems using optimized methods, specifically emphasizing the use of binary search for sorted arrays. This approach can help in decision-making and problem-solving during interviews.
-Utilizing coupon codes can significantly reduce costs, making it easier for individuals to access resources they need for career advancement. Consider using codes like 'take you forward' for discounts.
-Preparation for interviews is crucial, and utilizing algorithms like binary search can impress interviewers by showcasing efficient problem-solving skills. Understanding optimized solutions can set candidates apart.
-The ability to validate solutions is essential in problem-solving. Ensuring that selected elements from arrays meet specific conditions is a key step in achieving correct outcomes.
12:03 Binary search is a powerful algorithm for finding the median of two sorted arrays. It requires checking the validity of partitions to ensure the correct median is identified.
-Understanding how to find the median involves calculating the maximum of the left half and the minimum of the right half. This is crucial for determining the median correctly.
-The validity of partitions is essential. The conditions state that elements of the left half must be smaller than those in the right half.
-Adjusting partitions can be done based on comparisons. If conditions are not met, shifting left or right will help in forming a valid partition.
18:06 The process of finding the median from two sorted arrays involves determining the correct partitions, referred to as cut one and cut two. By ensuring each partition meets specific conditions, the median can be accurately calculated.
-Understanding the concept of partitions is crucial to finding the median. Each cut must represent a valid division of the two arrays for accurate calculations.
-Binary search plays a significant role in adjusting the partitions. By moving left or right through the arrays, the correct cuts can be established to determine the median.
-Comparing the maximum of the left elements with the minimum of the right elements is key. This ensures that the partitions are valid and helps in finding the median.
24:09 Understanding the process of finding the median of two sorted arrays involves partitioning and validating segments of the arrays based on their lengths. Proper handling of edge cases ensures accurate results in median calculations.
-The significance of edge cases in median calculations is emphasized, particularly when no elements are selected from one array. This ensures proper assignment of minimal or maximal values.
-The algorithm's adaptation for both even and odd total lengths of the arrays is crucial. Different formulas apply for calculating the median based on the length's parity.
-The implementation of binary search aids in efficiently determining the partitions of the arrays. This approach simplifies the process of finding the correct cuts for median calculation.
30:00 The explanation covers how to find the median of two sorted arrays using binary search. It emphasizes that the arrays must be sorted to ensure a valid partition for the algorithm to work.
-The process involves moving pointers to create a valid partition, ensuring the algorithm adheres to the constraints of the given sorted arrays. This is crucial for accurate results.
-Time complexity is discussed as log base 2 of the minimal length between the two arrays, indicating efficient performance during the search process.
-Space complexity remains constant at O(1), showing that the algorithm does not require additional space, further contributing to its efficiency in computation.
**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!!
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);
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.
Brilliantly explained. Can't thank you enough ❤️
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))
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
Hamre dronacharya ❤
Lil
Tb tumhe bhi eklavya banna padega.
@@willturner3440 haha
I truly appreciate you striver for explaining us with this much patience♥
Thanku for being our support
Holy shit....did he just explain this mind boggling problem so simply. Salute sirji.
I took GeeksforGeeks DSA course and I have to say this explanation is far far better than GFG's explanation for this question.
even I didn't understood gfg explanation
do you recommend taking the course?
@@DustZone033 if you're asking for the geeksforgeeks one then yes, I still recommend taking it. Most of the times, Sandeep Jain provide better explanation than any video on UA-cam. And also that dsa self-paced course has everything you need. All topics are covered with all approaches for every problem. And doubt solving facility is also there
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
hi Striver , Can this question be solved using the logic of matrix median ?
No, cause the answer need not be a part of the array here
Yes it can be. I solved using that logic and it passed all the testcases on leetcode
@@AbhishekKumar-vr7sh send submission link
Really good explanation. Very clear and concise explaining every concept used in this problem. Being grateful after watching your video. Thanks a lot folk.
I think the efficient solution works considering that elements in nums1 is less than elements in nums2. Also the case when any one of the arrays is empty needs to be handled separately.
yup I also had to handle the corner cases separately 😅
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??
Excellent one of the best logic and easily understandable .Thnk u so much
This one's an awesome problem!
Understood!
I went through so many videos for an explanation of this. Your explanation is the best.
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?
awesome explanation, makes a hard problem really simple with this explanation, thanks a lot!!!
This proves how in depth knowledge you have, just god level teaching, thanks a lot man.
Honestly mera faat gaya first time dekh kar... so I tried to skip and tried to find something better... But on watching more vid.... I realized that the video i paused and left was the best explaination. Thnx Striver....
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
@Striver,I have a doubt. Just assume the size of the first array is 6 and second one is 4(total 10). so we have to take 5 elements from both the array. but here high is initialized to n1(the size of arr1) in this case which is 6. how can we take 6 elements from arr1? 🤔..anyone knows abt this, pls comment.
n1 is basically the size of the smaller array.
why cut1 is only performed on smaller array other than making a small search space for binaryb search?
Striver Bro can you please cover dp problems from sde sheet after this, i have my exam in june, will remain thankful to you for the rest of my life 🙏
I think it won't be possible bro even for him ... he would have to go in a sequential manner! till then you could check out Kartik Arora's youtube channel for dp ... I have heard from many students that it is good...you could definitely check that out..! otherwise online resources are there only!
If you need to survive on someone else to make you successful you wouldn't be successful in the first place, these videos are good but not having dp videos should not be the reason for your failure there are many good resources on the web.
just a food for thought!
Best video on this question on youtube - thanks so much. Couldn't understand it until I watched this
I swear, if an interviewer asked me for the binary search method of this problem I'd be tempted to slap them.
The binary search method is beyond unintuitive, like if you never seen this problem, it is very very very unlikely you would come up with this on your own, especially in 45min
agreed
At the start of the video , i thought it is very difficult to understand. But the video went on, the whole things got cleared.
#Thank you #Striver
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 😊
Why do we always take the smaller array as the 1st array array and larger one as second ?
Binary search time complexity is log n, so smaller the N smaller the tc
why do the binary search on the most shorted array?
@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.
was struggling to understand it from past 2 days, but found this explanation!!! Amazing man hats off for such wonderful explanation
Well explained!! Only video I found with such a clear explanation!!
But why is it necessary to perform the binary search on the smaller array and not the larger one?
Log (search space length) is complexity. In order to have less complexity bro..
@@takeUforward No I tried it, it can give you an ArrayIndexOutOfBounds error if you use the larger array for binary search.
Try this:
Array 1 : [1,2,3]
Array 2 : []
Also if u dnt perform binary search on shorter array code fails for a case like : {0} {} . Dry run and try to perform binary search on the larger array u will understand.
@@ratnadeepbhattacharya3237 if any array is empty, why perform binary search? Simply return median..
@@takeUforward yes bhaiya bt in the code there ws no such condition that if an array is empty calculate directly(so it becomes an edge case) .... That's why the code gives error in the above test case if we do not do binary search on the smaller array always (i.e. if we omit the first if from the code).....so doing Binary search on the smaller array is important. I ran this test case on leetcode without the above if part and with the above if part to confirm. Btw thanks for the great work that u do......
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
Liked the way you worked backward from the result and framed concept from it. Keep it up
In your example, 12 !
Smart! Because it’s more efficient to pick the middle element for large quantities of elements, binary search.
Still Can't believe this content is available for free. Pure gold !!
#include
using namespace std;
double findMedian(vector &arr1, vector &arr2){
if(arr2.size() < arr1.size()) return findMedian(arr2, arr1);
int n1 = arr1.size();
int n2 = arr2.size();
int low = 0;
int high = n1;
while(low
int left2 = cut2 == 0?INT16_MIN:arr"2"[cut2-1]; you have assigned arr1[cur2-1] to left2; Correct it with arr2[cut2-1];
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
THANKS FOR THIS AWESOME EXPLANATION.
UNDERSTOOD ❤❤❤❤
I cant thank you enough Striver 🙏🙏
Your contribution is phenominal!
I have seen many videos for this problem. but your's right on the top. I totally understand the problem. thanku very much for this video
the way you explain is just like water.thank you bhaiya
@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)))?
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
My God, your explanation was so smooth, They ran out of butter to compete you!
After your explanation even hard problem sounded in my reach XD. Very well explained.
can't we do this question by simple binary search......... consider two variables low = min(a[0],b[0]), high = max(a[n-1],b[m-1]), we know that our answer must lie in this range. Take the mid element and apply lower_bound to find like how many elements are less than or equal to our mid. If count == median index which we can calculate. Then our answer must be max(last elements less than equal to mid in both arrays), else if count is less, than we can shift our low to mid+1 or if greater than shift our high to mid-1.
crystal clear solution !!!
Thank you so much striver😃😃!!
Do post amazing contents .
why is high initiliazed to n rather than n-1?
Failing at Test Case -
nums1= [2]
nums2 = []
Giving Index out of bound error
because it works only on smaller array
Why is it necessary to binary search on the minimum length array??
Best ever Explanation on UA-cam...........
I don't know whether you will read my comment or not.
But I want to tell you, you are doing extremely useful work for ordinary people like me.
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
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?
So the time complexity which u said O(n) is for the best case scenario right? Wouldn't it increase for the worst case?
it will fail for this input s1: [1,2,3,5,6], s2:[4].
can we do binary search on the array with large size instead of array with minimum size?
totally understood, and appreciate your teaching skills. it's amazing🔥
Why we have to do binary search on smaller array?why you change num1 and num2 on first line?
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 :)
Understood. such an easy explanation of this complex solution. You just created one more fan ❤
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!
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 .
What is time complexity of the statement n1 = nums1.size() ?
Is it O(n) or O(1)
this code will fail for these two arrays
[1,2,3,5,6]
[4]
correct me if im wrong.
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???...
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..
Do we need to put extra conditions like if any of the array size is zero or both of them are of size 0?
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?
If we use this algorithm in merge sort then the sorting would become faster (from nlogn to lognlogn). Right ?
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
Why we are doing binary search on always smaller size array ?
Why are we taking hi as n1, not max(n1,n2)
Hi Bro, Could you please explain why we are doing binary search on smaller array?
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
Best explanation :)
Understood !!!!!