Binary Search : Median of two sorted arrays of different sizes.

[@shrimatkapoor2200]

I love when he says "once it hits you" like some kind of drug or something

[@Alex7nt]

@Kayden Khalil Lol, that is scam! fake accounts

[@nishantkumar1149]

It's a better than a drug and the dopamine released on solving questions is sickkkk.

[@JCatharsis]

It finally hit me I'm so high rn

[@nikhileshkumar9126]

don't do drugs bro. It's harmful.

[@ncba]

Quite a common phrase

[@dakshays6375]

Damn !!! How did anyone come up with such an Algorithm

[@balajim7801]

Clear explanation. Thanks. A small error, 8:33 value of "end" should be 5 (size of small array). I followed just your example and coded, everything was right but failing always, until I watched your code & realized that end should have initial value of smallest array's length.

[@eskuAdradit0]

any clear explanation on why would we do it like this? is it the same reasoning behind adding + 1 to the sum of both arrays before dividing by two?

[@haoyuwu894]

@@eskuAdradit0 I think it's because in some cases we can have all the elements in x on the left side. He mentioned that partitionX is "the number of elements partitioned to the left in x." So in those cases, partitionX can be the size of the small array. Consider this example: arrayX: [1, 2, 3, 4] and arrayY: [5, 6, 7, 8]. All the elements in x are smaller than elements in y. Hope this helps.

[@kimmeng6939]

7:18 end should be 5 not 4 because we are searching which position we want to cut.

[@prakashtiwari7834]

YES! Had the last element of first array been 10 instead of 15, the algorithm would've broken at 13:45. Anyways, the explanation was awesome.

[@everydayleetcode2961]

@@prakashtiwari7834 I was wondering why did he take end as 4 and read this comment ! Thanks a lot !

[@emilyhuang2759]

But why not 4? The 5th index is empty....so I would think the end is 4...?

[@sharmamukul938]

@@emilyhuang2759 Exactly even i'm not able to figure out why the end should be 5 and not 4 as it is clearly mentioned in the video that first array has 5 elements in total.

[@varunwalia95]

@@sharmamukul938 it should be the size of the array not index that is to be taken as high element according to code.

[@anupbid]

I need one explanation, please help me here guys.. at 8:08 he sets start at "0" and end at "4" before the binary search starts but in 20:25 if you check the code using the same arrays in the upper timestamp you will see that he has set low as "0" but high as "5" (the length of the array) instead of "4"(the last index). Now, this code works but not the explanation which would require the high to be at 4, to begin with.. Can anyone help me here plz?

[@beer_bandhu]

This is amazing. I was so confused by this problem, you explained it so succinctly. Thanks

[@uzdik.student]

00:00 Introduction 01:39 Solution 06:19 Example 1 14:35 Example 2 20:11 Code

[@abhinavgarg5611]

Thanks buddy😊

[@suvirsaurav5587]

In the first example, the end value at the start should be 5 as we can have a partition when all the 5 elements of array X will be on the left side.

[@ADITYAKUMAR-yd3ow]

Perfect explanation, initially I though it would be difficult for me. But gradually you made me understand in only one go. Thanks 😀

[@tusharroy2525]

Great.

[@nik220287]

Man the way you explained it in the first 5 minutes just clarified everything. Thanks. Great video!

[@barmalini]

I paused the video at 20:12 and now going to solve the problem at leetcode myself, thank you so much Tushar, your help for the rest of us who have never graduated from the CS but still want to become a sane programmer is invaluable

[@marshallxu7480]

this is the best video of all time, it brings happiness. thank you!

[@prasadwants]

bro tushar please make a video on how to prepare for giant companies like apple,amazon etc. also thanks for the amazing video

[@tusharroy2525]

I will try.

[@83rossb]

What do you think this entire channel is for?

[@Roger-rf7yp]

Thank you for sharing! This hard problem on Leetcode is understandable by any folk with the basic knowledge of median and binary search! That's really crystal clear explanations!

[@RAHULRAJ-rv4ng]

Tushar Roy - Coding Made Simple Sir, please make some more videos on binary search, and explain the strategy how to apply binary search, and please provide the explanation of the code on the github, the circular binary search problem on the github. Thanks

[@clumsycoco]

@@83rossb Lmao!

[@double_courage57]

@4:30 - I took a second to understand this : Think of the final sorted array (without duplicates) and draw a median line. We need to find the average of numbers which are immediately to the left and right of that median line. If x2 is immediately to the left of the median line, it has to be greater than y5 (remember final array is sorted). Similarly, if y6 is to the right of the median line it has to be lesser than x3. Hope this helps someone!

[@TheBuzoTechie]

thanks for the extra intuition :)

[@return1210]

Thanks a lot!

[@maxfeldman6654]

probably one of the best explanations i have seen so far, SUBSCRIBED!

[@emilyhuang2759]

7:21 What do you mean by +1 allows what to "play well with both odd and even number of elements in the combines array"?

[@CinghAnkit]

So that we have extra element on the left side , where we are looking for median. listen from 9:59 ,it might help you.

[@sshangrou8799]

thanks very much.it took me long time to think the algorithm on leetcode, your explanation is so clear and concise.Very nice

[@chilly2171]

Why do i need to +1 on 9:05. This guy does not explain.

[@chentang514]

24:03 I don't understand, for each loop, we only have an increment by 1 on both sides. This should be O(n) because it does not seems like a binary search for me. Ideally, we should start in the middle, and decide to go left or right halfway. I didn't see how that represent on the final code page.

[@louislouis117228]

@Chen Tang Although we only have an increment by 1 on both sides, we do the increment on low. Then we still need to do the "partionX = (low + high) / 2", so it is exactly a binary search. . 哎呀，同是用中文的同胞，用英文表達有點彆扭... 如上所述，雖然他每次都是+1或-1沒錯，但+1或-1的對象不是 partionX 而是 low 或 high，而每一輪 partionX 都還要再 /2，所以確實是 binary search 沒錯。 舉個例子： x = 1 6 7 8 y = 2 3 4 5 第一次迴圈 low = 0, high = 4, partionX = (0+4)/2 = 2; 第二次迴圈 low = 0, high = 1, partionX = (0+1)/2 = 0; 第三次迴圈 low = 1, high = 1, partionX = (1+1)/2 = 1; 然後就結束迴圈了。

[@vivek4490]

at 2:36; it would be great if you could provide some details as to why we need to choose y partition at y5 in accordance to chosen x at x2. Thanks!

[@remixisthis]

Very well done detailed explanation. Much better than the LeetCode solution example. Thanks for taking the time to make this!

[@rohitkumarratnesh4780]

Why applying Binary Search on the smaller array ?

[@程龙-b1w]

I was plagued by this problem for a very long time, you made it crystal clear, sir. Thank you!

[@SonuSonu-tk5pk]

very neat and excellent explanation

[@tusharroy2525]

Thanks

[@MikhailVainarevich]

Thank you for explanation, Tushar. It is really great for understanding the logic. One thing I'm struggling to understand is why this method is O(log(n+m)). When the condition is not met, we increment the 1st half of smaller array by 1 and check again. In the worst case, we are going to do it n/2 times. Isn't it O(N) time complexity?

[@hilarious_metabolism]

We moved by 1 due to how the example data looked like. The key insight is that we divided X into half (think of the division by 2). For the next iteration the middle of X became the start of the new interval within which we conduct the next search iteration.

[@KD-xi9wu]

What is the logic of extra +1 while finding partitionY can anyone please explain me?????

[@adityapaithon6499]

who else came here from that shitty leetcode article?

[@meganlee5897]

Brilliant video and explanation! One minor change to the 1st example:initialization: 1) pick smaller len 2) start = 0, end = len, binary search the len of left size of X e.g with the first example: 1st round lo = 0, hi = 5, mid = lo + (hi - lo) / 2 = 2 2nd round lo = mid + 1 = 3, hi = 5

[@anuragmishra5346]

In example -2 if X ={1, 26, 31, 35}, partition X will give wrong partition because it will give partition X =0, however, it should be partition X =1

[@leetcodevideowatcher8253]

I have the same question!

[@rajasekharmaddineni1069]

To move left or Right of array, should increase or decrease on "start" and "end" variables. not partition x because it's failing in below case [1,2,3,4,6] [5]

[@GeetThaker]

it is working. remember you have to make 2nd array as X in example.

[@gurmeetchawla8362]

you have explained it very well, But I am wondering if somebody is asked this kind of problem unless they have already solved it like this or the solution is known to them in advance how will they solve this in the interview in a short time.

[@hindustanimusiclover6543]

For most interviewers, it would be enough if you provide the O(m+n) solution , the would probably let you know that this can be done in logarithmic time and try and guide you to this solution.

[@nikhil199029]

No SIr, it wouldent be enough!! They will expect the solution in log N time!! (provided u targetting google/amazon/microsoft type companies)

[@neeralm4849]

I was asked not exactly this, but a very similar question in a very recent interview. First thing to realise, is that it can obviously be solved in an iterative manner, and so the interviewer is not looking for that answer. But say it to the interviewer, that you can obviously solve it by combining. Second thing to realise is, in sorted arrays, there is always a chance of logarithmic solution. Then start thinking in that manner. That's it. If you start thinking and talking about your thoughts, the interviewer generally helps, and with little luck, it would be solved. I found that talking about your exact thought process with the interviewer really helps.

[@praphael]

@@hindustanimusiclover6543 No, most certainly will not be enough.

[@abhinavmiglani6587]

The variable end should be input length of nums 1, Consider case: nums1 = [1, 3] nums2 = [2]

[@junxuchen2851]

How would the algorithm deal with the case [1,2,3,5,6] [4] For the first round: start = 0, end = 5, partitionX = 2 and partitionY = 1, But the second round: start = 3, end = 5, partitionX = 4 and partitionY = -1, what should I do of this -1?

[@adityagoyal50]

That's why he takes the smaller length array to be the first array. Try with this [4] [1,2,3,5,6]

[@Varun-uv4li]

@@adityagoyal50 one question for you. why this is logn solution,????? at worst case it will be O(n/4) which is O(n).

[@CarmelleCodes]

Great video! Thank you!

[@AmitKumar-we8dm]

Fails in number of testcases like x= [1,2,3,5,6], y= [4] and x=[2], y=[], etc

[@utsavdahiya3729]

We always take X as the smaller array, so this condition does not arise.

[@stratonov]

Beautiful lovely brilliantly handled edge cases

[@shivangishukla2629]

why x+y+1/2 , why did we add 1... i didnt understand!

[@pi3ni0]

Thanks, good explanation. I was looking for different resources, but it was the best so far :)

[@bhaviksheth3672]

Can someone explain to me why the +1 in (x+y+1)/2 - partitionX?

[@barmalini]

To guarantee that the left side will be equal or larger than the right. That is, if I have understood it correctly

[@umeshpatnaik5174]

This is to get the median . +1 is for the odd number length . see the median is a number which is situated at the center of the merged sorted arrays . lets say the length of total is 4+5 = 9 ; then if mid will be 9/2=4, so we have 5 elements on the left 0-4(5 elements )and 5-8(4 elements) on the right . if you have the mid of 1st arr : (0+3)/2=1 . so you have 2 elements of 1st array and hence you must have 3 elements from 2nd array to get the median .Hope it answers your question

[@sajo7304]

If x=1 and y=2 then partition x is 0 and y partition is (1+2+1)/2 -0 = 2 which already past the elements of y

[@AjaySingh-xd4nz]

Thank..very nicely explained!! I have a doubt. Could you please explain @18:45 what if 11 was not less than 23?

[@anondoggo]

Beautiful solution, thank you so much! I can't believe how close I was to the solution, I wished I pushed myself a bit harder, but this was a great educational experience. Thanks again!

[@venkateswarank1145]

I wonder where from earth he got this fantastic idea. @Tushor How do you actually frame this idea ? Where did you start first and how did you end up with this idea ? Kudos Tushor

[@navjot7397]

This is not his idea, he is just trying to explain an already existing algorithm.

[@jessica_1811]

came to "like" this video only found out that I have "liked" this video 4 years ago when I was looking for my last job. Thank you Tushar.

[@DonchenkoNadia]

Tushar, thank you so much! You explained it perfectly! If someone need solution in Python, here it is: class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1); x = len(nums1) y = len(nums2) low = 0 high = x while low

[@gunahawk6893]

clean implementation good job

[@angadthandi4136]

Might totally be a noob question: You are using: "lo = 0, hi = x" with "while lo

[@bitbyte8177]

same doubt

[@jasonmeyer495]

Great video, thank you. One question: "If the combined array is odd length, then we will have 1 extra element on the left side". What makes this so? What makes it such that it's never the right side that has 1 extra element?

[@olbap250]

I think it's because of the +1 in the formula partition x + partition y = (x + y + 1)/2. It makes it so that when the combined array length is odd, when you divide by 2 you're getting that one extra element in the total number of elements from the two left partitions.

[@zaheenrahman6608]

My boy Tushar Roy! Earned yourself a sub! Gonna help my algo course so much

[@sck29]

Excellent code buddy. Thank you

[@rushivt]

I have seen many other videos for this problem, but yours is the one that made me follow every step clearly. Thank you!

[@zixinliu6957]

Hi Tushar, I am confused, in the first example , x has 5 elements and in the second example, x has 4 elements, why do both of them have start = 0, end = 4? In the first example, is the end 5 I think?

[@Namast3-travels]

He says in his description it was a mistake in example 1 and should be 5

[@zixinliu6957]

didn't see that, thanks

[@USIndian51]

If you are using pure binary search, the mid index is (min index + max index)/2. if you don't know the max index, which is the last index in an array then you compute it as 0 + array size - 1. Assuming the indexing in array starts from 0. In my opinion the first example has to be 4 and the correction is needed for the second example. Tushar?

[@harsh9509]

No buddy, correction is needed in example 1 only because if we have array X of size 5 , then we can partition it in 6 ways ---> 0 elements on left and 5 elements on the right => partitionX = 0 ---> 1 elements on left and 4 elements on the right => partitionX = 1 ---> 2 elements on left and 3 elements on the right => partitionX = 2 ---> 3 elements on left and 2 elements on the right => partitionX = 3 ---> 4 elements on left and 1 elements on the right => partitionX = 4 ---> 5 elements on left and 0 elements on the right => partitionX = 5 so partitonX can vary from 0 to 5 so end should be 5 and if it would not be so, and instead end is 4 then we would never obtain value of partitionX = 5; :)

[@sinharakshit]

Wow I'm so glad someone asked this question and I'm even more glad that people responded with comprehensible answers! Phew! I would've racked my brains out otherwise 😅

[@shaziasamreen8584]

Even after 5 years your video is best for this problem.Thank you so much for wonderful Explaination

[@WS-lv4kk]

For odd total array size, instead of adding 1 in the (x+y+1)/2 and taking the max of the left half, I think you can just do (x+y)/2 and take min of the right half.

[@pavithranravichandiran6720]

Great observation!

[@soulmusic6530]

after reading multiple explanations, this one finally made me understand how to think. Thanks for the video.

[@peasant12345]

Why the complexity is of O(logn) if you just move one unit in each case when the partition is not properly found.

[@whatthetrip2226]

i have exactly the same question, after first iteration where we pick middle element, we are only moving linearly, an increment or decrement in partition at a time, how can it be O(log n) then?

[@peasant12345]

@@whatthetrip2226 use binary search on either high or low

[@gavin8535]

Why plus 1 in (x+y+1)/2 ?

[@fatiharslan7849]

14:43 you are saying end is 4 here but it's 3 if we compare with the previous example

[@sunilmehrotra1380]

Hi Tushar, yes, I also have the same doubt. Please help

[@abhijeetpatnaik5494]

I can't stress enough, how clear this video explanation is. Really loving your work, and it's very very helpful.

[@13379056]

With brute force you can actually achieve O((m+n)/2) with constant space. Just don't store the merged elements and end the merge once your reach the m+n/2 element

[@deleteduser792ba]

That is true but there is no such thing as O((m+n)/2) since 1/2 is a constant and it gets eradicated in the asymptotic analysis. Nonetheless, what you have proposed is a "better" linear solution.

[@PMPhotographyVideography]

The base logic is very well explained in this video. Problem is at 7:05 where you don't explain how you came up with that formula.

[@srivathsanvijayaraghavan6523]

We want to find the median of the combined elements of the 2 arrays, hence (x+y+1)/2. I believe the +1 is there to ensure the solution returns the element in the middle when the combined length of the arrays is odd.

[@adithyabhat4770]

Thank you!

[@RitikSharma-pc5yj]

Isn't this more of the same to a median of "Running input stream" where we need min-heap(1) and max-heap(1) but here we are more of virtualizing them? :)

[@frankfrank306]

So basically I am not smart enough to be able to crash this in a 45 min interview, so I tried to memorized the solution but I can't because I do not know the f*** what the code is doing. But after watching your video, I can actually memorized the solution because of your explaination. Big thanks and f*** those interviews.

[@hksubs]

Thanks, this code is clear. the vars maxLeftX and minRightX . . . help clarify. BTW, code works without "+1" for partitionY and using for odd case: "min(minRightX, minRightY)". I ran it on the "L" site.

[@harmanbirrai5676]

In your code .. if I dont add +1 to (x + y +1 )/2.. and in case of odd length of total array I do min(minRightX, minRightY) .. i get the same result from all test cases .. any reason why you used +1 and did max(maxLeftX, maxLeftY)

[@ciceanwang1621]

seems need check int partitionX = (low + high)/2; int partitionY = (x + y + 1)/2 maybe overflow, Integer.MAX_VALUE + X, or define as double , but there is no constrains menthion in the question

[@Royceroni]

Sorry, you lost me at around 2:21-2:23. You started drawing arbitrary lines at x[1] and y[4[ which didn't really make sense nor did you explain it. I think you were just using it as an example, but I think the example would have been much clearer if you used actual #s. I think you should have swapped the next section with the section starting at 2:21

[@anikgtx]

2:26, let's suppose we are partitioning x array along this point, (taking 2 from beginning) (Why ? ) and then you say , "in that case we have to partition y at this point (takes 5 from beginning) , (why? ) You should have explained why you are taking first 2 on the x array and due to that why you are taking 5 from y.

[@poonamshelke8797]

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?

[@fancyAlex1993]

I have watched Neetcode's and Striver's explanations for this problem, but neither of them come close to this 6-year-old video.

[@hemanthreddygayam6807]

Solution is completely wrong Input X = {1,2,100,110,120,130} Input Y = {3,4,5,6,7,8} It should be 6.5 but it returns 53.0

[@shubhamgupta9778]

Thank u bro.... Your video always give us very good concept..... Please make a session on josephus problem. This problem is very easy to understand but hard to implement.

[@ivankozlov1592]

Thanks for the explanation. My only concern is that my code fails for x = [1, 2], y = [3, 4]. On the last iteration when I split the arrays as [1 | 2] and [3 | 4] with low = 1 and high = 1. The algorithm will increase low and will not pass the loop condition(low

[@GuraseesSingh]

Once you increase low,I feel the new split would be [1,2 | INF] and [-INF | 3,4] which would satisfy the condition. The algorithm makes sense in this case, however I have not looked at the code.

[@uditagrawal6603]

you started with high = x or high = x-1? This problem arises when you start with high = x-1 works finw with high = x.

[@chenlee7934]

@@uditagrawal6603 Why should hight start with high = x?

[@efraimrodrigues]

I coudn't find the four elements mentioned at 4:16 for these two vectors: X=[1,2,3,4,5] Y=[6,7,8,9,10]. Am I doing something wrong?

[@shubhammishra3783]

Finally understood the problem thanks sir

[@SaraH-dj8xg]

why binary search on the shortest' length array? why not any one?

[@blasttrash]

you can do binarysearch on longest length array also but it wont be efficient(micro optimization though). The reason this works is because imagine total length of the array is 10 and I ask 8th largest element, you can search for this from left(you will travel 8 iterations). on the other hand I can search from right(I travel 2 iterations). Thats the main idea. If you partition the total array in the question(m + n elements) into two, then the left half will contain some elements from array1 and also contain some elements from array2. lets say that array2 was 2 times larger than array1, then the above left half will contain x elements from array1 and 2x elements from array2. Essentially its proportional contribution. Smaller array will have lesser elements and larger array will have more elements in array. This is assuming that they are equally sorted. If all small numbers are in array1 itself, then left partition will contain all array1 elements.

[@SaraH-dj8xg]

Thanks so much for the thorough explanation. Couldn't have said it better!

[@chandansharma-ek9jw]

1. how u come up with the formula partitionX + partitionY = (x+y+1)/2 ??? 2. how +1 in x+y+1 is helping for both odd and even case??

[@unmeshjoshi5948]

For the partition you have just mentioned that we can add +1 to make it simple. But if the interviewer asks for a reason what should we say? If I just say it will make it simple will it not sound like I have already seen the question and I remember the solution. Could you please suggest what reason we can give

[@PhoenixRisingFromAshes471]

Jahapana tussi great .........sir i read a lot about this problem solution everywhere but finally came to understand from your video only...you made a very tricky concept so simple to understand

[@李冬-h1v]

Thank you, it's very helpful.

[@kevintran6102]

Thank you for sharing. One thing to notice is at the second example (15:21) end should be 3 not 4, right?

[@Ved3sten]

I don't understand how someone can think of this during an interview? Is it based purely on memory? Like there's thousands of questions on Leetcode...

[@dartvv2219]

Thanks for explanation but this code is not working on simple test data int array1[] = {1,3}; int arra2[] = {2};

[@dipendersingh1536]

Maan gye sir aapko 😏😏

[@vastavp]

Around 5:14. Why are we assuming the extra element is on the left side? Why cannot it be on the right? I know I'm missing something. Can't figure out what.

[@ankitpradhan8177]

can we do with this approach like ? please reply sir 1) merge two arrays in the third array using the merging code 2) sort that third array 3) then using a for loop find the middle element and that's the Median !!

[@an_other_world]

every element on one half is smaller than all the elements on the OTHER HALF OF THE OTHER ARRAY

[@kshitijtakarkhede7833]

Crystal clear sir

[@pawandeepchor89]

Excellent !! Nothing more one can do to explain this problem :) Thanks for sharing it buddy !! You are a star, keep up the good work, cheers !!

[@owenkhoury6756]

Why are you moving the partitions one position at a time? Shouldn't they be splitting the numbers to the left or right of the partition by half on each iteration? Otherwise how is this solution Log(n)?

[@asgarh4589]

The first 6 minutes are the most important, else u will find it difficult

[@2radix774]

Ive spent 2 days on this problem reading a couple of articles about this problem explaining it and I still dont understand it and how to solve it am I stupid/

[@vikasaggarwal2834]

i usually don't comments on videos but your method of explaining made me comment on this... Superb video boss..

[@mahipalsingh-yo4jt]

thanks for your solution and very easy explanation. I tried geeks for geeks solution . But its was very hard and took two days of mine.!

[@suryac850]

Damn, this guy made a video on this question 6 years ago. It is 2024 and I was asked this question in an interview.

[@mulikshrikant9639]

let x=[ -43, -25, -18, -15, -10, 9, 39, 40 ] let y= [ -2 ] this test case does not get passed

[@somiljain896]

The best explaination with perfect testcases that I found for this question on Internet. Thank you!

[@hksubs]

thanks Tushar. What do you think of example 1? Mr Meng wrote of this too. The 'end' in ex1 is wrong; in ex2, it's right. In ex1, the end=4, but it should be 5 since length is 5. In ex2, end=4, which matches the length.

[@MrJackytonny]

Thanks a lot for the great Explanation! May I know why high has to be set to the length of the array? instead, I used to set high = len(arr) - 1 in a Binary Search. So could you please explain this point as well?

[@VinayRachapalli]

In general we do binary search with indexes as low and high, here we are using size as low and high. in case of indexes it varies from 0 to n-1, in this case of partitioning it varies from 0 to n.

[@akarkessel]

Poor explanation, sorry. The tricky interesting part is done quickly, with no example and any proof

[@BasavarajBagewadi]

The initial value for "end = 4" is wrong.It should be 5. Cos the lenght of the array 1 is 5. Correct me if i am wrong