Median of 2 Sorted Arrays of different sizes | Binary Search | Data Structures and Algorithms

𝐂𝐡𝐞𝐜𝐤𝐨𝐮𝐭 𝐝𝐞𝐭𝐚𝐢𝐥𝐬 𝐚𝐧𝐝 𝐞𝐧𝐫𝐨𝐥𝐥 𝐟𝐨𝐫 𝐨𝐮𝐫 𝐋𝐈𝐕𝐄 𝐜𝐨𝐮𝐫𝐬𝐞𝐬 𝐡𝐞𝐫𝐞-
www.educosys.com
The video contains following parts-
0:00-1:00 - Question Introduction and example
1:00-3:00 - Brute Force approach with small optimization
3:00-8:15 - Logic behind need of partition
8:15-9:35 - Condition for correct partition
9:35-12:25 - Changing wrong partitions to correct one
12:25-15:53 - How to find partition - Binary Search
15:53-22:14 - Code
22:14-28:30 - Dry run for example
28:30-30:00 - Complexity
30:00-31:08 - Odd number of elements case
#dsa #softwaredeveloper #interviewquestions

[@KeertiPurswani]

Hi guys, Should have covered one more point - you should apply binary search on the smaller array only otherwise you will end up getting error. I have covered the point of exchanging the arrays at around 29:30 but didn't exactly say that this is a must do otherwise will lead to error. Thanks to so many of you who tried writing the code and pointed it out. I left this point for the end coz I thought it would be confusing in the beginning but I should have put more emphasis on this. Thank you and happy coding! ❤️

[@shubhamagarwal2998]

a=[100000] b=[100001] i guess it won't work bcz l1=-inf , r1= 100000 l2=100001 r2=+inf so (l2

[@shubhamagarwal2998]

oh it is working my bad...... i was putting "hi=n-1" but as soon as I put "hi=n" it worked ... can't caught this annoying things in binary search...

[@abhijithkashyap4537]

Can you explain the reason for the error or the scenario where you get the error. In this video you do the binary search on the bigger array and it seems to work correctly, isn't it?

[@gamingblast2325]

Mam can u explain why there is error when you run binary search on larger array ?

[@Aditya-pl3xg]

@@abhijithkashyap4537 because there is possibility that cut2 will go out of bounds if we take larger array for binary search.

[@battlecrusecruse9155]

avoiding this question from the past 3-4 months , and finally found this beautiful explanation .

[@KeertiPurswani]

Yaaaay 😇😇

[@smackdown9441]

@@KeertiPurswani how come you teach so simply these tough question 👍🙏 mam

[@ru2979]

DIDI ROCKS 🔥🔥

[@udayptp]

You are my bro😍

[@anishchandgothia4197]

Achaaaaaaaaaaaaaaaa

[@sarthakagarwal8499]

Great Explanation!! I watched 4-5 videos of the same problem but still found it hard to understand but she made it clear. When I was about to exit the video, she said not to be worried as it is a hard one and stay till the end, so I stayed and I am glad. Also, timestamps were a great add on, not many creators bother to put them. One more thing, pls don't dislike(if you can't like) this video as it is almost half an hour long video, just imagine how much effort she must have put in this.

[@KeertiPurswani]

Thank you SO much Sarthak!! ❤️❤️ That is so sweet of you! I am glad you stayed till end. While saying that stay till end I was wondering if I should say or not, but so glad that I said it 😇

[@harishchandrasekaran7839]

Didn't understand the first 10 mins when I was watching this in the evening with a disrupted mind. Sat down at 6am the next morning with a calm mind and got everything! Great explanation! Keep up the good work!

[@sudesh6807]

Folks who are finding it difficult please watch multiple videos by different KZbinrs and visit back again. Hard problem require different perspective and examples to understand properly.

[@nehadeshpande6119]

I could not find a better explanation than this on the whole internet, for this problem! Thank you, Keerti :)

[@kajawali7516]

It is the easiest explanation in whole KZbin, u teach important thing "we need why to understand how".

[@satyaadityabaratam35]

crisp and clear. Most importantly you are just addressing what a viewer might get struck at. Thank you so much

[@gautamjangir8927]

The best explanation in the entire youtube.....Thanks.

[@prashantmohan2233]

This was literally the best explanation of this problem available on youtube.

[@KeertiPurswani]

Thanks Prashant. Means a lot 😇 I hope you like rest of my content as well 😊

[@ShahinAnsari-e6s]

One of the best explanations I got online. Thank you.

[@oknokok]

Finnally understood the logic here. Nice explanation 👍

[@shivangsharma4873]

Great explanation, In the starting I didn't understand much but till the end when you dry run the test case the solution is crystal clear by itself. Thank you for so patient and detailed explanation.

[@sushmitagoswami2033]

I just like how you explain things with so much calmness. Kudos Keerti!

[@himanshugupta7010]

seriously escaping from that question from past 2-3 months 'coz the explanations avail were very confusing . thank you so much for explaining with such a great precision.

[@Anonymous-uj3jx]

The Best explanation for this question on KZbin in 2022

[@NikhilKekan]

becomes clearer and clearer slowly, thanks

[@saicharanreddy6379]

the best explanation of all the videos on the same problem.

[@DebabrataDas-xl5or]

Thank you so much for such a beautiful explanation Finally I realized why we are doing what we are doing.

[@rahulbhati3079]

BEST EXPLANATION, REALLY IT IS AMAZING. EVEN FROM YOUR HARDWORK I GOT MOTIVATED .

[@KeertiPurswani]

Thank you SO much ❤️❤️ means a lot 😇😇

[@Francis12345ify]

I loved this solution, I loved how you labelled everything on the board. Made it so much easier to process. Thanks!

[@lokeshnandanwar9203]

I watched 3 different videos for the same problem. This is the best crystal clear explanation. Kudos to you. Here is the Java code I have written. public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1); int m = nums1.length, n = nums2.length; int low = 0, high = m; while (low r2) { high = mid1 - 1; } else if (l2 > r1) { low = mid1 + 1; } else { return (m + n) % 2 == 0 ? (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0 : Math.min(r1, r2); } } return -1; }

[@adarshkunwar8113]

Here's the C++ Code if anyone needs it and the explination was on point,thx:- double FindMedianOfSortedArrays(const vector &A, const vector &B) { int n1=A.size(),n2=B.size(); if(n1>n2) return findMedianSortedArrays(B,A); int l=0,h=n1,mid,mid2; while(lr2) h = mid-1; else if(l2>r1) l = mid+1; else return (n1+n2)&1?min(r1,r2):(max(l1,l2)+min(r2,r1))/2.0; } return 0; }

[@adarshkumar-ys9tp]

[2,3,4,5] [1] some modifications in the code... *we need to keep n1< n2, if not pass the arrays in the function to make it n1

[@KeertiPurswani]

Thanks for this, added pinned comment 😊😇

[@sarveshchavan4391]

Thanks bro

[@ziminfan1664]

This is the best explanation I've seen so far after watching almost all top videos about this question! The only problem with me is I'm not very used to the accent and so I have to slow down the speed to 0.8-0.9x.

[@namansharma2320]

You have explained very well Ma'am. Please upload more videos of data structures and algorithms. And thanks for explaining this problem in a simple way.

[@KeertiPurswani]

Many videos coming up Naman. Thank you 😇

[@kartik5134]

This is the best explanation for this problem. understood it.

[@shivanimehta5280]

Procrastinating the problem for so long, but not anymore. Just crystal clear 🙏

[@KeertiPurswani]

Yaaay ✌️✌️😇😇

[@shristip519]

12:39 Thank You so much, this was needed. This problem has an expert tag in gfg. I couldn't follow Tushar's explanation although it was my incompetence but finally I understood this. Thank you for your effort!

[@KeertiPurswani]

Glad you got it. Happy coding ❤️

[@chaitrapvasista7041]

Very detailed explanation and the diagrams actually helped visualize the solution!

[@cpwithsundar]

WoW! All i can see is 5-6 hrs (even more than that) of hard work just to make us students understand a complex and hard solution in 30 minutes. It was fantastic ! Loved your in-depth explanation and analysis.

[@KeertiPurswani]

Thank you so much, and honestly it's much more than 5-6 hours 😅😅 Hope you like rest of the videos as well!! 😇😇

[@ceciljoel9577]

@@KeertiPurswani how long did it take you to solve this problems completely? is it reauired to he gennady level in software dev or not?

[@alphacoder3822]

Hi di, I think its not your approach that makes these vdeos interesting but the explaining on the white board that is making the defference. I understood it completely this time. Thank you

[@lalit-singh-bisht]

without a doubt this was the best and on point explanation for this question.

[@utkarshsharma5202]

Why we take end1 = n1 and not n1 - 1 because we are taking begin1 = 0 as from 0 to n1 there are n + 1 element and in all searching problem we take low as 0 and high as n - 1?

[@rhitamdutta1996]

The best video on this specific problem, subbed!

[@khushable]

You have explained with so much patience...kudos to that..i will need to re-watch once again to understand fully...here's to understanding better ... cheers

[@KeertiPurswani]

Thank you. Hope you understood everything!! 😇😇

[@mr.curious1329]

You can make as good as a teacher as you do as a software engineer!! You have the flair for teaching!! Very good!

[@anchalmishra2322]

Very Cristal clear explanation didu tnku bless uh😘

[@b_01_aditidonode43]

this explanation is a masterpiece in itself, mam!! whenever you said, that "it is a hard one so, stay till the end", it gave me immense power and the level of clarity you have provided is unparalleled, highly grateful for the efforts😁

[@KeertiPurswani]

Thank you so much! Means a lot! ❤️😇

[@deviprasadchand]

This is hands down the best explanation to this problem....thank you.

[@saurabhparwani9874]

Finally understood the whole solution & intuition. Thanks a lot for clear & detailed explanation.👌

[@KeertiPurswani]

So glad it helped! Hope you like rest of the videos as well 😇😇

[@saurabhparwani9874]

@@KeertiPurswani Of Course Mam . Even I have sent you connection request on LinkedIn.

[@himikhemani888]

Thank U.Thorough Explanation.Was facing difficulty,Now It's interesting. Thank You Mam

[@himikhemani888]

Was facing difficulty in understand 'Kth Largest Element in Two Sorted Array'.After watching this video I got the backbone of it.

[@siddhantsharma8066]

Amazing Explanation!! You always make sure that each and every aspect of the question is covered properly. Thanks a lot!! :)

[@mahee96]

Notes for myself: Concept: Find approximate positions where the two lists are grouped into left and right such that max(left)

[@akashprajapati7988]

Thanks mam I was trying to understand this ques from many months. Now I've understood properly. Great explanation ☺️☺️☺️

[@ChetanMishra-id8er]

dry run clear all the intuition behind that stuff good job

[@surendharv795]

Thank you Keerthi.......for the extraordinary explanation..

[@prathamgupta992]

Thankyou so much. I was stuck at this problem for weeks.

[@sleepypanda7172]

I liked it a lot. You are really good at explaining the logic. It was like I was thinking along with you. Looking forward to watch more videos whenever I feel stuck at LC. Kudos to your efforts.

[@chandrikasaha6301]

Very good explanation! I had tried binary search, my solution got accepted but it was still not optimal. I went through couple of videos and this was the best

[@divyanshuraj4085]

you have amazing teaching skills , loved that

[@nobody8272]

Best explanation for this question🔥🔥🔥Sorry to say but while watching the video, my mind often goes to your beauty rather than the video itself☺️

[@Perldrummr]

Thank you very much for this explanation! I'm sure I'll be going back over it once or twice before many interviews.

[@KeertiPurswani]

Hope you like other videos as well. Thank you ❤️

[@akshaypawaskar1585]

Hi Keerti, Very clear explanation of the problem. But I am not sure of statement that "We can do binary search on any of the arrays". When trying to run code on array1=[2,3,4,5] and array2=[1], performing binary search on bigger array array1 low=0, high=4 Iteration 1 cut1 = 2 and cut2=0 l1= 3 and r1=4 l2=Integer.MIN_VALUE and r2=1 since l1>r2, hence high=cut1-1=2-1=1 for next iteration Iteration2 low=0, high=1 cut1=0 cut2=2-0=2 which is causing ArrayIndexOutOfBoundsException, since array2 has only 1 element in it However if we always do binary search on smaller array, we dont run into this problem. Please let me know if I am missing something here.

[@KeertiPurswani]

Hi! Thanks for asking this, checkout the pinned comment 😊😇

[@debaratighatak2211]

I was stuck with this problem since several days,finally understood the solution.Thanks for such an amazing and detailed explanation! :) ❤

[@KeertiPurswani]

So glad toy understood it ❤️❤️ Hope you like rest of the videos as well. Please do share the channel with your friends. It would mean a lot to me 😇😇

[@yashrajsingh8181]

Best explanation on KZbin!

[@sheikhmkrifat7749]

It would be great for beginners if you provide code sample of some common language and thanks for the nice and clean explanation.

[@rajraorane7338]

thanks for being so patient and reiterating imp points again.

[@KeertiPurswani]

Hope you like rest of the videos as well! 😇😇

[@hv_harshit]

Very good explanation , wasn't able to think of a solution like this before. By the way one corner case is failing for this solution - [2,3,4,5] [1] here in 1st go it will give us value like- l1= 3 r2 = 1 l2 = MIN r1 = 4 after that clearly (l1 > r2) so will do hi = cut1 - 1; hence new high will become 1 in next iteration cut1 = (1+0)/2 = 0 cut 2 = (4 +1)/2 - 0 = 2. //issue so when we do l2 = cut2==0 ? INT_MIN : arr2[cut2-1]. // this will give arrayIndexOutOfBounds So we should take n1 as size of smaller array. hence we can swap the numbers. like- if(nums1.length > nums2.length){ return findMedian(nums2, nums1); }

[@KeertiPurswani]

Thanks for this, added pinned comment 😊😇

[@reelcutsandtrilers5036]

Finally I found the best explanation of this question in the whole universe!!!!! #clear kr diya concept

[@KeertiPurswani]

Yaaaaaaaaaayyyy #khushk kr diya comment

[@SandeepSingh-un9uu]

Here the main concept to digest is why L1

[@aakashyadav6228]

Watched your "Median from data stream" and "Interleaving strings" video and now for topics which I search on youtube I always check your channel before going to others. Great explanation. Thanks !

[@KeertiPurswani]

That's means so much to me Aakash! Hope you always find solutions here. Thank you ❤️😇

[@AbhishekKumar-gg6ox]

Such a high quality explanation. Thanks Mam..!!! I loved that you gave enough time to explain every bits and pieces and this is commendable. Just one correction, I think hi = n2(size of smaller array), the reason behind is that suppose arr1 = [1,2,3,5,6] and arr2 = [4] , then if you keep hi = 5, then there may be a case where cut1 = 4, then cut2 = (4+2)/2 - 4 = -1 and this will create trouble. So, always hi = n2(size of smaller array) for equal partition of elements.

[@KeertiPurswani]

Hi Abhishek, I have covered this point at 29:00. Didn't want to confuse beginners in the beginning of video itself 😊 I am glad you liked the explanation. Thanks! 😊

[@akarkessel]

The best explanation on internet for this problem!

[@KeertiPurswani]

Thank you so much 🥺🥺❤️❤️

[@martinharris4416]

The motivation in between was much needed 😭😭 this was a hard problem

[@KeertiPurswani]

I hope you got the whole thing by end of the video?

[@martinharris4416]

@@KeertiPurswani Yep, i just need to code it myself once and it will be clear !

[@KeertiPurswani]

I hope you will do that soon. Let me know! 😊

[@mystryb345]

Very good explanation I was no able to understand after watching too many video.Now everything is crystal clear

[@KeertiPurswani]

So glad to know 😇❤️

[@anshumansharma4580]

Terrific Explanation, Ma'am. Crystal Clear!!!!

[@KeertiPurswani]

Thank you so much ❤️😇

[@diveshrajput572]

Such a awesome and cleared explanation . Thank you so much ma'm.

[@KeertiPurswani]

Thanks Divesh. Glad you liked it 😇

[@sankalpchapalgaonkar3137]

Amazing video Keerti. Really appreciate. Very well explained.

[@sanchitbatra4431]

generally during binary search we take the last index as high , that should be n1-1 , why did you take n1 as high to start off with?

[@roshanmhatre8810]

Very detailed and most clear explanation🔥 for this question on KZbin, Could you please make an explanation for the same question but array with same sizes 🙏

[@ibknl1986]

A very good explanation. Thank you.

[@AbdifitahAbdulkadir]

This Sister you I left my course video on this concept now watching your code and video but I can you tell me why I am having one extra value when I use (n1+n2)/2 and then need to use min(r1,r2) . what is that property tellme ? I tired few trail examples and I am always having one extra ? why that is true and what is behind that calcualtion ? is there any mathematical property of that ? because you immediatly said"you will have one extra value for that calcualtion" ? thank you I wll watch again your video but I would like to know this Idea.

[@ps6846]

best explanation till this time for this question

[@KeertiPurswani]

Thank you 🥺❤️

[@AnshuKumar-zn1qb]

Best solution I have ever found ... Great explanation mam

[@KeertiPurswani]

Thank you Anshu. Means a lot 😇😇

[@nurshuvo3854]

Absolutely amazing explanation.

[@apurvabandi2962]

Firstly, thank you for your time and patience in explaining the solution in so subtle way. Loved your voice as well :) So I tried to implement it in java but I am getting runtime error for ex: [2,3,4,5] and [1]. Here is the solution I tried based on your explanation: Can you please let me know if I am missing any edge case scenario? class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; int lo = 0; int hi = n1; double l1; double l2; double r1; double r2; int cut1; int cut2; System.out.println("lo hi s:" + lo + "~" + hi); while(lo r2) hi = cut1 - 1; else if(l2 > r1) lo = cut1 + 1; else{ if(((n1+n2)%2) == 0) return ((Math.max(l1,l2) + Math.min(r1,r2)) / 2); else return Math.min(r1,r2); } System.out.println("in loop lo hi s:" + lo + "~" + hi); } return 0; } }

[@KeertiPurswani]

You aren't exchanging the arrays. Binary search should be done on the smaller array Mentioned it at 29:00. I know I should have mentioned it earlier. Many people had the same doubt. What I thought at the time was that mentioning in the beginning could be confusing while understanding the question. Hope your solution works now. Let me know!

[@ajayhajare5175]

This is the ACCEPTED code on Leetcode in Java. Hope it helps! class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; if(n1>n2) return findMedianSortedArrays(nums2,nums1); /*This line is not given in code by Keerti.We need to keep n1< n2, the reason behind is that suppose arr1 = [1,2,3,5,6] and arr2 = [4], then if you keep hi = 5, then there may be a case where cut1 = 4, then cut2 = (4+2)/2 - 4 = -1 and this will create trouble*/ int l = 0, h = n1; while(l

[@kirankutte7073]

Hello @keerti Purswani, atlast why we have to consider the smaller length. Because i ran the same code with the greater length ,its not working . Could you please me tell why. Thank in advance !

[@dikshamittal5827]

Hi Keerti ! I have recently started seeing your videos, for this one specially I must say you have just done an awesome job.

[@johnnyf1624]

thank you, your explanation is the best. it was rlly good when you applied the test case

[@ranbirsingh4472]

Very well explained Keerti Di.Thanks for making video on this .I have gone through lot of articles and videos. Finally got clarity after watching this wonderfull video. Thanks a lot.The way you are helping us is really appreciable. Wish you to stay healthy and keep posting such videos.

[@KeertiPurswani]

Thank you so much Ranbir. It really means a lot 😇😇🙏🏻🙏🏻

[@sameekshabhatia2219]

Thank you so much for explaining it .It helped me a lot .Really appreciate your efforts.

[@KeertiPurswani]

Thank you Sameeksha. Hope you like rest of the videos as well ❤️😇

[@marlegagaming1274]

I could only think of merge and return median ? Without knowing the solution, is it possible to come-up with this in an interview ? 🤷‍♂️🤷‍♂️

[@rt_developer]

Best Explanation of all the recommended videos✌👍

[@KeertiPurswani]

Thank you so much. Hope you like rest of the videos on the channel as well ❤️😇

[@rohitdatta1103]

Just had a doubt in partition l1

[@lokeshnegi5051]

finally i get to understand this algo. really great explanation ,this video deserves more views.

[@KeertiPurswani]

Thanks Lokesh. Please do share the channel with your friends and help it get better reach 😇 Hope you like rest of the videos as well. Keep sharing your feedback!

[@editorera239]

Keerti mam If possible keep making these tutorials These are helpful for beginners Thanks

[@codingwithanonymous890]

getting this apporach would be bit difficult during interview unless you have already did something like this before. Thanks for explaning so well :)

[@kanna2k4]

Thanks a lot mam, this made me clear to understand this problem 🙂

[@rohitk472]

Explanation is really good ,,,, Thanks di 😇😇😇

[@Kuriocity]

For Binary Search, why are we taking high = arr.length and not arr.length-1?

[@balajimysore7732]

HI Keerti, beautifully explained first the intuition and then the approach to write the code, starting with binary search and then optimizing. Please keep doing these amazing videos of hard problems. You rather communicate very clearly😀

[@Prashantkumar-pn6qq]

Can you explain the reason for the error or the scenario where you get the error. In this video you do the binary search on the bigger array and it seems to work correctly, isn't it?

[@AlokRatnaparkhi]

Best explanation on the internet..more power to you👌

[@KeertiPurswani]

Thank you so much. Please do consider sharing the channel with your friends 😇

[@AngadSingh97]

Thank you Keerti Di, really clear explanation

[@adrikagupta5573]

Thank you so much for this video! The way you teach is really good and your efforts to leave no stone unturned to make the students understand this hard problem is extremely appreciated.

[@KeertiPurswani]

Thank you so much. Means a lot 😇

[@aditisrivastava6499]

Wonderful explanation.

[@prasantharavindramesh1078]

Hi keerthi.Fantastic teaching.ill try out the code today with even and odd sized arrays.Can i use the same approach to find out median of 3 sorted arrays?

[@varuntaneja7073]

Your channel is going to blast once youtube starts recommending you to more people. I've watched a few of your videos and the explanation is just amazing ...flawless.

[@KeertiPurswani]

Would you instead help me by sharing the videos with your friends? 😊

[@varuntaneja7073]

@@KeertiPurswani for sure . I'll do my best to help you reach your first milestone 😁

[@KeertiPurswani]

Thank you. Means a lot 😇😇

[@shubhamchandra9258]

Amazing explanation. This really is quite tough question for a lot of people. You explained the solution with great ease and clarity. Looking forward to more such amazing content. Thanks.

[@madhusaivemulamada3556]

Thanks for sharing your knowledge. One of simplest explanations I have seen. Keep up the good work 👏