Median of Two Sorted Arrays - Binary Search - Leetcode 4
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
Code on Github: github.com/neetcode-gh/leetco...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/median-o...
0:00 - Read the problem
1:45 - Drawing explanation
14:05 - Coding explanation
leetcode 4
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#median #facebook #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
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
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.
Then grind more 😂
@@user-ib3ev5pl2t dude shut up. you would never solve this in 45mins having never seen it before. foh
@@user-ib3ev5pl2t 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
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.
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.
Thanks. I was looking for this explanation
Ahh that makes sense ty!
Thanks champ!
this is well explained!
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
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.
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?
@@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.
@@clintondannolfo714 I see, thank you, that's helpful!
It's hard LC and these are rarely asked in interviews
But i did :)
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!
I wish you'd picked two example arrays where one wasn't contained within the other. Would have made things a bit more clear
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
Yes! Was wondering what on earth I did wrong when this dawned on me. Python was made for this question
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!
Yeah... it really is!
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
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.
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
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!
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!
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 !
Thank you for explaining the core concepts of the algorithm - this was super helpful
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.
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;
thanks, just what im searching for!
Great point. In typescript, this works similarly. So, you should write:
const i = Math.floor((l + r) / 2)
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!
Only a couple re-watches? You're super smart
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 ❤
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.
Yeah, `//` is the floor division operator, not integer division.
You are a lifesaver, man. I was literally struggling to understand how it would work if the division keeps giving 0 instead of -1.
Yeah it was bugging me a lot, thanks man
Yea man you saved 3 hrs of my life.
yeah, we can use this function in java "Math.floorDiv(i+j, 2);"
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
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
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
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)
Thanks, I thought nobody else noticed
(max(3,3)+min(4,4))/2
@@toekneema I also noticed , but during my second watch.
@@toekneema I noticed
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.
Thank you, this problem was bane of my existence for a long time
By far the best explanation for Median of Sorted Arrays I ever got!
Great job!
Keep up!
Your explanation is so clear! Thank you!
Very clear explanation! You've made my day!!
In c++, you have to use floor((l + r) / 2.0), otherwise you will not pass [1,3][2] test
yep, python // is specifically floor division. That caught me off guard when translating this solution to another language.
Thanks, been scratching my head on it for an hour.
Thnx man
Greatest explanation ever! Clean n clear
great explanation, thanks for going through examples.
very clear explanation !! Thanks a lot !
This is the best explanation (including the official leecode explanation) I could find.
1. The most thing I hate about binary search is to set the ending condition, such as while l
Very clear explanation. Very helpful. Thank you Sir.
Excellent explanation! Thank you so much!
I used to hate this problem and kinda avoid solving it. But because of your clear explanation, I finally can solve it. Many thanks!
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.
Excellent! You're a LIFE SAVER
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.
very clean code and well-explained! Thank you
Glad it helped!
Thanks Neet! Keep em coming
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.
Super intuitive explanation, thank you NeetCode!
Finally an explanation that I was able to understand. Thanks legend 🙌🏻
Wow one of the toughest questions made look ridiculously simple. Lot of edge cases. Missing your videos past 2-3 months.
I really like your approach style, keep going together
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!
I comprehended about 80% of that so thank you! I'll rest my brain, probably rewatch, and hope for a 100% tomorrow.
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.
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
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
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
this is so clear and understandable, thank you!!!! :)
Clearest explanation ever, thanks you so much!
No problem 👍
the best sol i found for this prob, thanks brother
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.
For this puzzle, this is probably the clearest explanation online....
I like your video so much, really appreciate it!!! Do you have a sheet summarizing all those 273 videos as you did before for the 75? Like, including difficulty level, problem title, and category.
Thanks for the understandable explanation.
What a clean code .. thanks man
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
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.
Think about the case where A = [] and B = [1]
Very Clear Explanation..
Thank you so much
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.
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.
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?
Thank you. Very well explained!
Clear explanation, helped a lot!
This explanation is so clear!
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.
The only problem is that it is not actually O(lg(n)). See comments above.
Thx for the infinity trick. Couldn't come up with it. I really scratched my head trying to solve the edge cases
i was able to do this by myself but it took an entire day of brainstorming.
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
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!
Best Explanation. Thank you so much🤩🤩
This question is super hard for me. Thanks for the explanation!
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
This was a fantastic explanation
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❤
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)
Thank you for the explanation! :-)
Thank you again NeetCode!
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.
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?
I have exactly the same question
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.
If either of the input lists is empty, and the other one consists of few enough elements, one seems to get out-of-range errors on assigning values to Aright and/or Bright due to the expression 'i+1 < len(A)' and the equivalent one for B always being true.
Am I missing something?
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.
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 :)
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).
Amazing explanation!
Thank you for the great explanation. What tool do you use for drawing?
Thank you so much for these videos.
Good explanation, thanks!!!
Thank you for your brilliant work🤗
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.
I was wondering the exact same thing
What do you mean? He is doing mid ± 1
You're a life Saver
Superb teaching!!!
Wonderful explanation !
Thanks!
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.
The Code explanation is NEET 😀👍👍👍👍👍!!!
crystal clear thank you!
super talent on explaining !
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)
because (i + 1) + (j + 1) = half, due to 0-index
Love the visuals
Amazing explanation. Thanks
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...
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
I love this explanation!!!!
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")
Thanks for the brilliant solution.
Why does while r>=l not work here? If we use that, what changes would we have to make to the code?
If you had the r>=l condition for the while loop, it would break out of the loop in the case when you don't take any elements from the smaller array as the left half, for example A=[0,1,2,3,4,5], B=[7,8,9]. So in such a case, the median will be at the index 'half' of the larger array if 'total' is odd, or the average of the values at indices 'half-1' and 'half' if 'total' is even.
So you will have to write the code to check if total is odd or even and return accordingly after the while loop.
While it's okay to do so, I personally feel that would be like a repetition in the code, as we are implicitly dealing with the above case when we set the out of bound values to -infinity and +infinity and run it as a while True loop
I solved this problem only thanks to your explanation, thank you very much
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.