Median of Two Sorted Arrays - Binary Search - Leetcode 4

[@NeetCode]

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

[@stupidfrog]

Easily the hardest LC problem I've ever come across to date. This solution makes sense, but there is no way anyone is coming up with this in a 45 min interview lol

[@AndreiSokolov-k7j]

what does an interview even entail? They want an employee who has experience in a certain field and they test it with tasks. Yes, it's a difficult task, but it just shows whether you've had experience of problem solving in general. If there weren't enough neurons to come up with a solution, it means you don't have enough experience. But that doesn't mean you have to memorise every task, you don't have to. You just have to solve a lot of problems and memorise the patterns themselves. So if a person was experienced, had enough neurons to solve this problem, then he is fit for the job. If he could not solve this problem, it means that he has not solved similar ones, it means that he does not have a general knowledge of patterns in this area.

[@votanlean]

Then grind more 😂

[@michaelc8638]

@@AndreiSokolov-k7j dude shut up. you would never solve this in 45mins having never seen it before. foh

[@wassafshahzad8618]

@@AndreiSokolov-k7j A yes cause obviously having experience in the technologies used in the real problems is less important then grinding leetcode. Yeah he is right no one is coming up with this solution if he hasn't seen this problem before hand

[@nomad_1997]

You're either a genius, or you memorize it. Pick and choose. That's what I've learned grinding LC for the last two months.

[@AlokRatnaparkhi]

For those who are wondering about -2 on the Line 13, for more readability you can rewrite this as : int partitionY = half - (partitionX + 1) - 1; //PartitionX is 0 indexed so you need to add 1 to exactly know the size of partition 1. Then you subtract it from half to know the size of partition B. Once you do that extra -1 at the end because we want to calculate index of partitionY. Partition should be 0 indexed as we are dealing with arrays. Even if you calculate this, you get half - partitionX - 2 in the end.

[@amitbansal7754]

Thanks. I was looking for this explanation

[@LavanVivekanandasarma]

Ahh that makes sense ty!

[@m_elhosseiny]

Thanks champ!

[@trsdesrn5246]

this is well explained!

[@DevanshGoyal..]

I used it by default in my code and I was shocked that he used it too because no one on youtube has used this strategy for solving this problem

[@binetlee2534]

Love your style of explanation, I was familiar with the log nature of binary search, but I couldn't wrap my head around the logic of what elements to choose each time. Your drawing of the partitions in different colors made a lot of sense, so thank you!

[@clintondannolfo714]

I've asked candidates this question for years at a Big Co and never once had a candidate successfully answer using this approach (after many interviews). Only a few even attempted it (but it wouldn't pass tests due to errors) and afterwards if candidates suggested it I only talked about it briefly to see their understanding and suggested them to do an easier solution. I feel like if I ever was made to implement the binary search version of this during an interview I'd fail, it's not really intuitive at all and neither is it telling me if a candidate is good or bad. Plenty of good people won't be able to get this in an interview, the false negative rate will be astronomical.

[@atreides4911]

is there a reason why you were asking this problem if it was so bad at detecting positive signals? were you told to do it?

[@clintondannolfo714]

@@atreides4911 because I wouldn't expect the fully optimal solution. It's used just as a point for discussing about the problem and working through it, and getting some kind of working code. That part is where you get the signal, the signal is not from the solution itself. For myself anyway.

[@atreides4911]

@@clintondannolfo714 I see, thank you, that's helpful!

[@draganostojic6297]

It's hard LC and these are rarely asked in interviews

[@graceng9921]

But i did :)

[@m_elhosseiny]

Thanks! Just a small note, can you give more difficult examples when running through the algorithm drawing? I feel it makes it validates your solution more rather than the ideal case which sometimes makes the viewer doubt wehter this would work with edge cases. for eg: you used 2 sorted arrays starting from 1 increasing by 1: [1,2,3..etc] with one smaller than the other in length. I would've loved a second example were you use another set of arrays.

[@AndreiSokolov-k7j]

As far as I'm concerned he shows the direction in which to think, and there can be so many cases and that will make for a great video. I think it is better that the video is not too big and shows the main point of the problem

[@Philgob]

There's too many edge cases for some problems. As a business, he has to stay in that sweet spot of video length from 10-25 minutes. You just have understand the algo yourself and write out the edge cases you want if you're not conviced

[@ankitasinha3727]

For people solving it in Java, replace line#12 with int i = Math.floorDiv(l+r, 2); As mentioned, Python integer division // behaves different than languages like C/C++ and many others. In Python, if you type -1//2 you get -1 whereas in other languages you'd get 0

[@benpurcell591]

Yes! Was wondering what on earth I did wrong when this dawned on me. Python was made for this question

[@ax5344]

whenever I tried to search for a problem and i saw your video--- although it is not on top---it feels like such a relief! Thank you, please do more!

[@srinadhp]

your videos are like watching an engrossing edge of the seat thrillers.. The way you uncover the solution and the clean code are unparallell. Thank you!

[@sankalparora9374]

Yeah... it really is!

[@roman_mf]

Took me a couple of re-watches to finally get that 'click' to understand your way of thinking. Amazing solution as always. I would say it's less about binary search itself and more about the logical thinking: we don't care about how the array will be partitioned, but we do care about rightmost value of left partition and leftmost value of the right partition. Knowing these values we can easily figure out the median value. Just brilliant. No way I would have ever came up to this solution by myself, let alone come up with this solution during the interview!

[@tlz124]

Only a couple re-watches? You're super smart

[@lovuitchen9332]

Enjoy your videos, high quality and pythonic. Thank you! Just one note, it seems a "mistake" during explanation, at around 12:26-13:00, where it should be max(3,3)+min(4,4)/2, right? Because you wanna upper bound for the left arrays and lower bound for the right array, I believe.(which is correct in the code later actually--around 20:29)

[@toekneema]

Thanks, I thought nobody else noticed

[@SreenathV]

(max(3,3)+min(4,4))/2

[@rohitkumaram]

@@toekneema I also noticed , but during my second watch.

[@xuxiangyu7025]

@@toekneema I noticed

[@vishakarudhra8665]

I was totally searching for this comment. This should logically be the correct method for computing the median. The like from neetcode also confirms it, so that's a relief.

[@JackTheSpades]

Important note for those trying to solve this in different languages. Pyhton integer division // behaves different than languages like C/C++ and many others. In Python, if you type -1//2 you get -1 whereas in other languages you'd get 0.

[@PippyPappyPatterson]

Yeah, `//` is the floor division operator, not integer division.

[@crimsonghoul8983]

You are a lifesaver, man. I was literally struggling to understand how it would work if the division keeps giving 0 instead of -1.

[@nw3052]

Yeah it was bugging me a lot, thanks man

[@ayannaskar9195]

Yea man you saved 3 hrs of my life.

[@VinitRaj-ym4lm]

yeah, we can use this function in java "Math.floorDiv(i+j, 2);"

[@Dhruvbala]

I wish you'd picked two example arrays where one wasn't contained within the other. Would have made things a bit more clear

[@pranjal5451]

That's exactly what I said lol

[@nathanwailes]

I think in that case the binary search would just continue until one of the pointers went all the way to the other side.

[@lostdollars9945]

i really really appreciate how you humbly admit when a problem is hard even for you it gives so me much relief that ok maybe i'm not exceptionally stupid if a guy from google thinks it's a tough problem

[@symbol767]

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

[@ianokay]

I wish he elaborated on 17:03 where he states "Now any of these indices could technically be out of bounds", because it seems odd in a binary search for the middle to be OOB, but I get that his while loop is not doing "while l

[@EE12345]

The code actually fails if you do L R and the middle index becomes negative... but he didn't explain why exactly we need to do while True instead of L

[@gna6614]

I think it is related to the cases of: 1) if nums1 = [1,2,3,4,5] and nums2 = [100,101] then doing binary search on nums2 (the smaller array) and doing the comparisons will keep bringing the right pointer to the left because the mid will be always greater than nums1[j + 1]. The opposite is true if nums1 = [1,2] and nums2 = [100,101,102], it will keep pushing the left pointer to the right and will go out of bound 2) the case mentioned at 13:07 where one of the arrays are empty, which also means it's the shorter one so the mid pointer will already be out of bounds from the beginning Also I think a better naming than Aleft, Aright can be partition_a1_end, partition_a2_start I'm not sure if i explained correctly or clearly. Hope someone else helps in clearing this up

[@yashjoon3889]

If anyone coding this problem in c++ , remember that in python -1/2 gives -1 whereas in cpp -1/2 gives 0. So apart from coding the above code similarly in cpp add this check before assigning a value to i : int i; if(l+r < 0) i = -1; else i = (l+r)/2;

[@zachlin7192]

thanks, just what im searching for!

[@St1ggy]

Great point. In typescript, this works similarly. So, you should write: const i = Math.floor((l + r) / 2)

[@huangrex299]

Thanks for help me save time debuggins : )

[@vdyb745]

This is such a doozy problem !!! You have made my day with your clear cut explanation. I actually am understanding things which I thought I was too stupid to get !

[@WaldoTheWombat]

When doing a regular binary search on a single array, we cut the array in half each time to zero in on the item we search for. The same principle is implemented here, both of the arrays are sorted, so it make sense to check the middle item of each of them each and then searching in the correct part instead of just iterating from start to finish.

[@anujsinha6467]

Hats off man, I didn't felt confused for a single moment with formula or any this else, just dry ran the whole cases and every thing makes sense. Thankyou!

[@whatislove4044]

there is a mistake, you should start with l, r = -1, len(a) the code is invalid for this case [1,3] [2]

[@qixuanli4369]

Yeah. I run into a Time Limit Exceeded when the input was [3] [-2,-1] Your fix worked. Thanks!

[@kumaranp8764]

You are a life saver bruh

[@Syed-wj4pj]

can anyone explain why is that the case?

[@maratukhutdinov403]

Your comment was useful, but there is no mistake in his code:) He has "while True" loop, but I had a condition "while start

[@Slink1]

After watching this too many times to count, I finally understand some of the issues I have been having such as understanding how partitionY’s index is determined. You have no idea how impactful your videos are! Thanks so much ❤

[@georgeshaoyundong4590]

In c++, you have to use floor((l + r) / 2.0), otherwise you will not pass [1,3][2] test

[@ogdenmills9666]

yep, python // is specifically floor division. That caught me off guard when translating this solution to another language.

[@optimusprime5040]

Thanks, been scratching my head on it for an hour.

[@sarthaksuper284]

Thnx man

[@pinakadhara7650]

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.

[@MikhailVainarevich]

Thank you for explanation, 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?

[@slavaplek9875]

I have exactly the same question

[@pinakadhara7650]

We aren't actually "incrementing by 1" but moving the left pointer to "mid + 1". If you consider the smaller array's length as 11, mid = (0 + 11) // 2 = 5. If the condition doesn't match in this iteration, we move the "left pointer" to 6. Now mid = (6+11) // 2 = 8 I am not able to understand the why we are doing this though.

[@yuansyunyeh301]

I would like to suggest the 12 lines of codes may be modified for readable (15:32): i = (l + r) // 2 if (l < r) else -1 Because Python runs the codes doesn't expect the same with other languages. Thank you were sharing

[@Dhanushh]

Thank you so much. Busting my head for long time, why my Java equivalent isn't working. But can you explain how Python works without this change?

[@bryce.ferenczi]

​@@Dhanushh python rounds to -inf rather than zero, so -1 // 2 = -1 in python, whereas C++ -1 / 2 = 0

[@pepelepew4400]

Thank you for explaining the core concepts of the algorithm - this was super helpful

[@thelookofdisapproval8234]

Thank you, this problem was bane of my existence for a long time

[@OMFGallusernamesgone]

this question is crazy, how would you have known how to come up with O(log(m+n)) solution during an interview without having seen it before?

[@NeetCode]

Hopefully the interviewer would give you a hint, because I doubt I could solve it first try 🙃

[@TheGoya]

The part that's tricky to understand is where you increase/decrease the partition by 1, and why that doesn't lead to a degenerate linear case.

[@yejimmy3533]

yeah I also got the same question.. why this operation would not lead the time complexity to O(N/2) as only half the length at inital stage

[@tacticisacting3702]

that's not the partition being decreased by one, you have l and r values and i is in the middle of them, by setting r to i -1 or l to i+1 you halve the distance between l and r at each step so you get logarithmic runtime

[@tomonkysinatree]

The way you write the solution out in code, it seems simple, but I am almost certain the edge cases with this approach would have totally stumped me if I get this in an interview

[@world11191]

I comprehended about 80% of that so thank you! I'll rest my brain, probably rewatch, and hope for a 100% tomorrow.

[@yuurishibuya4797]

If ppl have not solved this before, it’s very unlikely that they can think of an optimum solution in the interview and code it covering all corner cases under 40+ minutes. Remember candidates have questions about team, work culture, etc as well to ask. I don’t know what knowledge about the candidate the interviewers will gain by asking these kind of questions. I have conducted a few hundred interviews, most of my questions tend to focus around what is expected to be known to work in my team from day one.

[@TypicalRussianGuy]

Hello, what your questions tend to contain? Asking to write a solution to a typical work-related issue? Please explain if possible. Also, by the way, these interview questions are not really designed to test a candidate. They are mostly designed to make it as hard as possible for a candiate so that a company could deny as many candidates as quickly as possible. It's kinda cruel, but it's one of the only ways companies like Google and Amazon can deal with the huge influx of people applying for a position.

[@darshanvanza3889]

Hello Neetcoder, I have a request, Could you please make a video on leetcode problem number 2387 (Median of a row wise sorted matrix). It would be helpful. By the way, your content is amazing and keep up doing this great work. Thank you for all of the efforts you made from all of the neetcode family members.

[@yitongxie6574]

Thx for the infinity trick. Couldn't come up with it. I really scratched my head trying to solve the edge cases

[@eshanpandey4186]

This is the first time Nav I felt that the explanation was not up to the mark, the explanation for why infinity and -infinity could've been better, along with a reason for Binary Search on one array will be sufficient, that too why on the smaller one only!

[@theghostwhowalk]

Wow one of the toughest questions made look ridiculously simple. Lot of edge cases. Missing your videos past 2-3 months.

[@yash1311]

Can somebody explain why r's values equates to len(A) - 1 instead or len(A) similarly why is the value of j equal to (half - i - 2) ? Any links to the explanation would also be helpful...

[@anukritibanerjee]

The reason for r's value len(A)-1 and not len(A) is because we considering the index. For a list A = [1, 2, 3], the index of 3 will be 2 i.e A[2] = 3 but len(A) = 3 which is out of bound since there is no value at A[3] and the reason for this behavior is because indexing starts at 0

[@MsSkip60]

Thanks for explanation, was asked this question this week and bollocks; it's too harsh for a phone interview despite it's not being a FAANG company!

[@tchovosky]

Love your answer, best I have seen so far. There are many others using recursion which make it really hard to understand. Yours is a variation of standard while loop with left/right pointers binary search. And it's much easier to code this way.

[@BarryBecker4]

The only problem is that it is not actually O(lg(n)). See comments above.

[@TheNishant30]

i was able to do this by myself but it took an entire day of brainstorming.

[@Donquixote-Rosinante]

How to use l

[@shinoharakenshin7496]

Just in case anyone else is stuck on trying to replicate NeetCode's code solution, for line #12 "i = (l + r) // 2" my replicated code was not able to pass submission but I managed to get all tests passed after I changed it to "i = (l + r) // 2 + l", the addition of l allowed me to properly use i as an array index to obtain the end of the first partition, without adding l its index would be offset from start of the entire array instead of from the actual starting position as marked by the l pointer. I also added the line "if (r-l < 0) i = -1;" under #12 to pass some edge cases. I don't know if this discrepancy is caused by misunderstanding on my part or if there was a mistake in the video, so I'm putting it up here if anyone knows.

[@scottk3292]

An edge case which I had expected to fail actually works correctly because the 'integer' (actually floor, not integer) division operator surprised me. With the shorter array having all values greater than the longer array, you end up with an i value of -1. I had expected -1 // 2 to be zero, rounding toward the origin, producing a wrong j index for the median, but I was wrong. The // operator always rounds down, even when dealing with negative results. In this case, -1//2 produces -1, so my fringe case still works perfectly.

[@Rahul-pr1zr]

Nice explanation! One thing which wasn't clear to me was - why are we always choosing to do binary search on the smaller array? I'm guessing because it's faster but is there another reason for it?

[@berkeevrensevdi1788]

I failed at input ([ ], [1]) when I chose bigger one. I think that when your merged array size is 1, you need to select nothing as left partition. But if you search bigger array, you actually start with selecting 1 as a left partition and it breaks the logic. So, you say that I am not going to choose any number for left partition but after that you select a number in bigger array for left partition. Also I failed at input ([1], [2, 3, 4, 5, 6]). Here, 3 numbers will be selected in left partition. When searching on bigger array, we initially choose [2,3,4] from bigger array and choose nothing from smaller array. So we compare bigger_left (which equals to 4) with smaller_right (which equals to 1). Since bigger_left is bigger than smaller_right, we need to narrow the partition of bigger array. When it is narrowed, we only select [2]. So, we need to select 2 numbers from smaller array but we are not able to do that since there is only 1 number in smaller array. I think that the amount of narrowing operation may exceed the size of smaller array.

[@crazyfootball2271]

This code will miss oner edge case. The smaller array (A in this case) , what if we have completed the BS and element is not found yet. It can happen when median resides in B and all elements of A is larger than MEDIAN elements

[@gunking1949]

tbh the best part of the code is switching to process the shorter array between nums1 and nums2 otherwise there is a lot of headaches when you move the pointer in an array that is much larger than the other

[@ilona7051]

I think you could just as well write 'r = i + 1' in line 30 instead of 'l = i + 1' (since the only time l appears in the while loop is in line 12: i = (l + r) //2 ). I think it makes more sense to increment the right pointer by 1 than to touch the left pointer.

[@paderborner5213]

Can somebody please explain at what part the "binary search" is happening? In lines 28/30, the right/left index is de-/increased by 1. I'd expect some halfing of an interval at some point, if a binary search was performed.

[@praveens5711]

We're decreasing/increasing the r and l pointers by subtracting or adding 1 to i and i is the value obtained by halving the interval at line number 12 :)

[@kai75785]

I fully agree with you. I believe this is worst case O(m), not O(log(min(m,n)). I see only 1 divide-by-2 and then a linear search. The "j = half - i - 2" is also just a guess which in his example works out perfectly but how about with (1, 2, 3, 4, 5) and (5, 6, 7, 8, 9)? You have to slide along about m/2 nodes - so it is O(m).

[@sankalparora9374]

By far the best explanation for Median of Sorted Arrays I ever got! Great job! Keep up!

[@ianokay]

It's an extremely unintuitive system using a binary search to try to randomly shift around the first partition until it isn't clearly incorrect. It's strange to even START with the premise "Okay so our left (merged) half is the left half of the smallest sorted plus the first rest of the longest sorted", and work from that, as it makes no sense why that would even work, and obviously if the smaller one is all larger numbers, it illustrates the nonsense, but the algorithm eventually works it out. It's just a strange pattern of thought since it starts with a premise that is immediately clear in making no sense and being incorrect, and then thrash around (semi efficiently) until a sensical correct solution pops out. What is weirdly unmentioned in this video is just the clarifying statement "What we're going to do is see how much of the smaller array we can use in the first half, by making the wildly incorrect assumption that it's the first half of it" (and it could be added "and correct our (almost certain) failure by moving logN instead of N+1, where we might actually over-shoot the actual correct portion, on behalf of a reduced complexity for large sizes of N")

[@vitzal3691]

For the wildly incorrect assumption, if the smaller array cannot be used in the left partition, the algorithm won't use it. That's the point of the binary search, it searches for the index of the smaller array to include into the left partition. When it doesn't include the small array in the left partition, the index (from the binary search) will be -1. This means, all the numbers in the left partition are those that are in the larger array (not necessarily all the numbers in the larger array). We won't overshoot the correct option on behalf of a reduced complexity for large sizes of N because the binary search will ensure that the left partition is constructed correctly by updating the bounds of that partition based on the maintaining the sorted order of the combined arrays.

[@ianokay]

​@@vitzal3691 > "For the wildly incorrect assumption, if the smaller array cannot be used in the left partition, the algorithm won't use it." I'm aware, and I stated that it will course correct the incorrect assumption. What I'm pointing out however is just that the initial state, the assumption made when initializing the algorithm, is unintuitive because the premise (which I described) makes no sense... so I find it hard for a person to intuitively/naturally choose that initializing state for the solution. > "We won't overshoot the correct option on behalf of a reduced complexity for large sizes of N because the binary search will ensure that the left partition is constructed correctly by updating the bounds of that partition based on the maintaining the sorted order of the combined arrays." You WILL overshoot the correct option, because instead of course correcting the incorrect assumption N+1 (which you could, and would make sense), you jump ahead (thrash around) randomly logN, to reduce complexity for larger sizes of N (exactly as I said) Please read more carefully when/if contributing to the conversation

[@seuntaiwo8735]

Thank you very much for all your solutions. They are really helping me a lot with your clear-cut explanations. For this question, I'm wondering why we have to ensure var A holds the array with the lesser length. At first, I thought it was to ensure a smaller time complexity but I decided to test. I removed the code ensuring A was smaller and a test case failed. Can you please explain? Thanks❤

[@Perrychen25]

If you don't assign the A with the smaller one, then you may encounter the case: A: [2], B: [] half: 0, i = 0, j= 0 - 0 -2 = -2 which will lead to ALeft: 2, ARight: inf, BLeft: -inf, BRight: inf and return min(inf, inf)

[@omartahboub2900]

The Code explanation is NEET 😀👍👍👍👍👍!!!

[@weiqianzhang981]

Fantastic video. Only one question. For this algo under the worst case, you actually need to move the pointer one by one till the end of an array and that may cause the time complexity to be O(m + n)? Because in order to get the log, isn't it necessary to move the pointer by half each time (not minus or add 1) so you can get the log part.

[@Lucas-br6rt]

I was wondering the exact same thing

[@mdazharuddin4684]

What do you mean? He is doing mid ± 1

[@fengliu975]

Still had to struggle bus for hours to get this but was able to attempt after watching first 2 min rather than having 0 idea like koko eats. These videos works man

[@fangzhongli9366]

I think this algorithm can also be applied to "k closest elements in a sorted array". After we find the closest index, we "partition" the array into 2 sorted halves. One half = target. And we can search for the range of the k closest elements with the method used here

[@ruizhu5295]

Your explanation is so clear! Thank you!

[@davidlohmann5098]

Could the same technique be used to find the median of 3 or more arrays of length n1, n2, n3, ... in O(log(n1 + n2 + n3 + ...)) time?

[@albertgao7256]

For this puzzle, this is probably the clearest explanation online....

[@brighttonyh]

Thank you for the video. The explanation is very intuitive. I do have one question, when actually implementing, what's the rationale of swapping array A and B (row 7 & 8 of the answer)? I wrote everything else the same but if I don't do the swap, it will fail at edge case when one of the array is empty. However I cannot think of why the core logic will fail if we don't sap

[@djslimcodes2337]

If you are familiar with Ultimate Binary Search, then using a lower bound to find the first right element from nums1, which is bigger or equal to the corresponding 'remaining' left element from nums2, might be easier: var findMedianSortedArrays = function(nums1, nums2) { if (nums1.length > nums2.length) { [nums1, nums2] = [nums2, nums1]; } const totalLength = nums1.length + nums2.length; const halfLength = Math.floor((totalLength + 1) / 2); let left = 0; let right = nums1.length; while (left < right) { const mid1 = Math.floor((left + right) / 2); const mid2 = halfLength - mid1; if (nums1[mid1] >= nums2[mid2 - 1]) { right = mid1; } else { left = mid1 + 1; } } const mid1 = left; const mid2 = halfLength - mid1; let maxLeft, minRight; const LB1 = mid1 -1 const LB2 = mid2 - 1 const RB1 = mid1 const RB2 = mid2 if (LB1 < 0) { maxLeft = nums2[LB2]; } else if (LB2 < 0) { maxLeft = nums1[LB1]; } else { maxLeft = Math.max(nums1[LB1], nums2[LB2]); } if (RB1 === nums1.length) { minRight = nums2[RB2]; } else if (RB2 === nums2.length) { minRight = nums1[RB1]; } else { minRight = Math.min(nums1[RB1], nums2[RB2]); }; if (totalLength % 2 === 0) { return (maxLeft + minRight) / 2; } else { return maxLeft; } };

[@IntelliStar_]

I used to hate this problem and kinda avoid solving it. But because of your clear explanation, I finally can solve it. Many thanks!

[@ianokay]

It's an extremely unintuitive system using a binary search to try to randomly shift around the first partition until it isn't clearly incorrect. It's strange to even START with the premise "Okay so our left (merged) half is the left half of the smallest sorted plus the first rest of the longest sorted, and work from that, as it makes no sense why that would even work, and obviously if the smaller one is all larger numbers, it illustrates the nonsense, but the algorithm eventually works it out. It's just a strange pattern of thought since it starts with a premise that is immediately clear in making no sense and being incorrect, and then thrash around (semi efficiently) until a sensical solution pops out.

[@harishsn4866]

Can anyone explain why (j = half - i - 2)? I didn't understand why we had to subtract 2. I thought subtracting by 1 is right. Please clear this doubt. PS: Thank you so much for your videos. I am hooked onto it.

[@cinimodmil]

+1 on this.

[@SP-go6lj]

there is a 0th index over 2 arrays so it needs to be -2 not -1

[@noufbouf]

I understand the code but I am not sure I understand why thats a binary search. I feel like the binary search should split some array by 2 at every iteration and thus obtain O(log_2(N)). What am I missing? Thanks a lot guys

[@kyryloyakovliev3688]

It does split an array by half since on each iteration either left or right bound is shifted by 1 from the middle index.

[@_thelegendaryduck_8523]

@@kyryloyakovliev3688 that is simply shifting by 1 with the worst case being n/2 no? this is very confusing

[@kyryloyakovliev3688]

@@_thelegendaryduck_8523 no, since, as I said, on each iteration either left or right boundary is shifted by the half of an array.

[@_thelegendaryduck_8523]

@@kyryloyakovliev3688 doesn't it shift from the smaller array by +1 ?

[@mehdiezatabadi]

Thanks for the great explanation! May I ask, what is the time complexity, I guess as your correcting the left side linearly, it is ~O(n)! Am I correct?

[@igorf243]

he swaps left with i+1 and i is len(Ai)/2 -> this is close to log(len(A))

[@symbol767]

Crazy how I'm back 5 months later and this algorithm is still one of the most difficult ones I've seen to solve optimally. Its insane how unintuitive this is. Any interviewer who asks this should be fired on the spot.

[@ata243y]

edge cases make this question hard i think

[@jpwengertv]

Clearest explanation ever, thanks you so much!

[@NeetCode]

No problem 👍

[@denysshushpanov7630]

I solved this problem only thanks to your explanation, thank you very much

[@hutlinh1830]

@neetcode thanks for your great explanation. Which tool you are using for drawing example section?

[@CasualyinAir]

very clean code and well-explained! Thank you

[@NeetCode]

Glad it helped!

[@balajeerocks3835]

Not working for below test case A: -43 -25 -18 -15 -10 9 39 40 B: -2

[@lianghe1401]

Looks working to me.

[@sauravus]

Excellent! You're a LIFE SAVER

[@slimahmed5631]

The solution that uses the 2 pointers approach is much more intuitive but i have to admit this way is more elegant & more creative

[@mixtli1975]

More intuitive, but much slower. It's N time instead of log(N) since you have to check every element of the array instead of binary search.

[@devdev19]

Does anyone know why you have to run binary search on the smaller array? I've tested it on the larger array and it fails on some instances.

[@moveonvillain1080]

Very important note: If you are trying to write the same logic in a different language keep in mind that Python's ' n//m ' does floor division meanwhile in languages like JAVA, C++ n/2 is Integer divison. So make sure to use a floor function on (l+r)/2. For JAVA int i = (int)Math.floor((l+r)/2.0); basically we find the double value of the division then it's floor and then convert it to int as the Math.floor() returns the value in double. This had me pulling my hair for an hour.

[@Allen-tu9eu]

the true god of leetcode problem teacher !

[@NeetCode]

Thanks!

[@AlexanderVishnevskiy-t5v]

I tried a similar approach but it was much harder). Initially, I searched for the middle index in the first array and then binary search on the second array. Time complexity O(logNlogM). I didn't know how to improve until I found this one. This solution is genius. Well done!

[@crazysapertonight]

Program did not pass test even after I copied your code line by line seems like some infinite loop is happening And I can't find problem

[@yb6036]

Change / 2 to / 2.00

[@rubberepileptic9833]

How are we going to solve this when we see it the first time? The first thing popped into my head was median of median and quicksort and idk what I am thinking

[@konradhunter1407]

I’ve been working on this problem for two days. 😖 My algorithm is a bit different but doesn’t work for the edge cases. Yours is much simpler and I’ll try it on my own now that I’ve seen it.

[@peanutbutter785]

This question is super hard for me. Thanks for the explanation!

[@stc2828]

I just wonder why isn't this O(min(n,m)) complexity. The worst case is when m = n and everything in A is smaller than B, it will take about m/2 loops to find the solution, which is slower than O(log(m+n))

[@michaelashkenazi1234]

You are right I thought about it too. This algorithm is not in the required complexity.

[@wesleychen4408]

No, because each time you are going to the midway point of the left and right pointers. In the worst case situation you need to do this halving process across the entire joint array, which is length m+n. The time it takes to do all the halving is log(m+n).

[@jaejincho9921]

@@wesleychen4408 I don't get it. Doesn't i simply go to the right or the left each time in the shortest array rather than being halved? For me it seems like to the maximum O(n/constant) so O(n) time complexity

[@BarryBecker4]

You are right. The algorithm as shown is O(n). To make it O(lg(n)) you need to modify the last few lines to be something like if (nums1LeftValue > nums2RightValue) nums1RightIdx = (nums1MiddleIdx + nums1RightIdx) / 2 - 1 else nums1LeftIdx = (nums1LeftIdx + nums1MiddleIdx) / 2 + 1

[@ashkan.arabim]

damn so such a sophisticated solution doesn't even generalize to more than two arrays

[@bhawansingla7920]

not working for input nums1 = [] nums2 = [1]

[@nehaa3778]

Thanks for the approach and succinct but drilling explanation. I like how the videos don't unnecessarily drag on but are totally value laden.

[@pooranik5342]

Very Clear Explanation.. Thank you so much

[@albertgao7256]

Could someone explain why `-2` in `j = half - i -2`; I do not get it, why both array start from 0 so we need to minus 2, should not it just for 1 array so minus 1 (I know it will lead to a wrong answer)

[@huyintang8407]

because (i + 1) + (j + 1) = half, due to 0-index

[@jerrybao1934]

Thank you for the video! I do have one question: at around 17:24, you said that in an edge case, i could be out of bound as i

[@oliverxie9210]

I have the same concern. I think `l` should start from -1 rather than 0. The algorithm never make the `l` variable decrease. So if the entire A array should go to the right part of the total array, there will be still at least one element(the A[0]) being put in the left part of the total array, which is wrong. The video is still very helpful though; I appreciate it a lot.

[@abdullahjavid]

Think about the case where A = [] and B = [1]

[@yejimmy3533]

Amazing video! may I ask in the pointer update (+- 1), why this operation would not lead the time complexity to O(N/2) as only half the length at inital stage? Looking forward your reply

[@holyjack5215]

Because i is the middle. So he shifts l or r for (l + r) // 2 each time.

[@kimmeyona8743]

you need to set l, r = -1, len(a) and including when a is []

[@Syed-wj4pj]

heyyyyy thankyouuu. this worked!!🏆

[@sandeshpaudel9665]

Can you elaborate on why you chose A to be smaller than B? I understand the argument that it's a smaller array to binary search and is thus more efficient. However, the algorithm actually wouldn't work if A is larger in size than B.

[@pinakadhara7650]

That's why if A is larger than B, he is swapping the arrays

[@blackcat_064]

Great walkthrough - I understood the solution really well in the end, except I literally wrote the same code as you (but in Java) and it kept getting stuck in infinite loops, when presented with arrays of length 1. I gave up cuz of this.

[@fadimichel1]

Thank you so much, that was very helpful. But there is a small mistake in the explanation at 12:30, I am afraid that someone is confused: Max(3,3) + min (4,4), not the opposite.

[@nathanwailes]

Here's my attempt at writing up what I think the logic is, just in case anyone else finds it helpful: 1. Our task is to find the median of the merged arrays, but do it in O(log(m+n)) time, suggesting a binary search approach. So what would we be doing a binary search of, and what would be the condition that would determine how to update the search and eventually end it? 2. We should notice that if the two arrays were merged, the median would be defined as the point where a left partition and right partition meet. So if there was some fast way to calculate where that partition happens in each constituent array (i.e. where each constituent array is divided into those elements that would be in the left partition in the merged array and which would be in the right partition), then we could find the median element in the required amount of time. 3. What we're going to do is do a binary search in the second array to find that partition point, thereby also finding the partition point in the first array (as I'll explain). We are going to compare the potential candidate values we identify in the second array to the first array to find the indices where each constituent array is divided into the segments that will go into the left and right partition in the merged array. 4. We start the binary search at the leftmost and rightmost indices of the second array as in a normal binary search. We take the middle of those, and that is our potential match that we want to consider (i.e. it's potentially the partition point in the second array). 5. A crucial insight is that by identifying that index in the second array, we also thereby know what the corresponding index must be in the first array, because the total length of those two left partitions in the constituent arrays must add up to the length of the left partition in the merged array. 6. A very difficult part of the problem is the comparison that then needs to happen to know if we've found the correct indices or not. We know if we've found the right indices if the end of the left partition in each constituent array is less than or equal to the beginning of the right partition in the other constituent array. 7. The other hard part is knowing which way to direct the binary search depending on the comparison of the two partition points. If the second array's partition point is too far to the left (the value is too small compared to the first array), we need to look to the right (set the left pointer equal to middle+1). The partition point is too far to the left if the first constituent array's left partition's last element is bigger than the second constituent array's right partition's first element.

[@mykytapiskarov7291]

Super intuitive explanation, thank you NeetCode!

[@qwerty-ol4gu]

Can someone explain it to me why its complexity is only O(log(min(n,m))?

[@mehmetalitoy3929]

Great explanation, thank you ...

[@likeXaXprodigy]

There's one part of you code that is a bit confusing: As you note, we need to handle the case where there are no elements of A in the left partition. This would presumably corresponding to `l = -1`. However, you set up the boundary conditions such that the minimal value of `l = 0`. Your code ends up working correctly only because in these cases `r` goes beneath `l`. While this technically works, this generally isn't how you expect binary search to work, so looks like a mistake. I think it'd be clearer to set `l = -1` as your boundary condition.

[@RaviChoudhary_iitkgp]

in the code, where we are considering the case where either all the element of the half of combined sorted array could belong to one of the array, that case may result to i, j out of the bound and since we are assuming to always consider the smallest array to start with i.e array A, to consider that edge case we need to initialize l with -1 since the edge case for array A could be the case where all half belongs to array B and the value for r with len(A) which corresponds to the case where all the elements of A could be the part of the half of the array. Hence small correrction to the code on the part where we have initialized l = 0 and r = len(A)-1 the correct initialization would be l = -1 and r = len(A)

[@benjacook3771]

One way we can check this if that if we replace the while True with while l

[@sarfrazahmad2580]

I tried doing it by eliminating values that can not be median by running binary search on both arrays. So at every iteration for both arrays you will get 2 inequalities which will tell max numbers of elemnts towards one side of the current value and get the min for the other. all values where min is greater than the max of the other (greater than 1 for even) will be eliminated (almost half the elements will get eliminated in each iteration)