Median of Two Sorted Arrays - Binary Search - Leetcode 4

0:00 - Read the problem
1:45 - Drawing explanation
14:05 - Coding explanation

leetcode 4

#median #facebook #python

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[jotrades]

if they ask me to solve this in O(log(m + n)), I am leaving the interview room in O(1)

[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

[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.

[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.

[clintondannolfo]

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.

[FifaHades]

That feeling when you reach the comments and see that everyone had a hard time, great explanation!

[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.

[binetlee]

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!

[ankitasinha]

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

[lostdollars]

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

[dthebala]

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

[ax]

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!

[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.

[lovuitchen]

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)

[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 <= r", BUT... and here's the. big but... HIS CODE HAS NOT YET ILLUSTRATED HOW/WHY THIS CAN HAPPEN.

[pinakadhara]

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.

[anujsinha]

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!

[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!

[vdyb]

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 !

[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!