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

  Рет қаралды 539,261

Tushar Roy - Coding Made Simple

Tushar Roy - Coding Made Simple

Күн бұрын

In example 1 end should be 5(not 4) since there are total 5 elements.
Find median of two sorted arrays of different sizes. Algorithm is based on binary search.
github.com/mission-peace/inte...
/ tusharroy25

Пікірлер: 721
@shrimatkapoor2200
@shrimatkapoor2200 3 жыл бұрын
I love when he says "once it hits you" like some kind of drug or something
@alienwareCL
@alienwareCL 3 жыл бұрын
@Kayden Khalil Lol, that is scam! fake accounts
@nishantkumar1149
@nishantkumar1149 3 жыл бұрын
It's a better than a drug and the dopamine released on solving questions is sickkkk.
@JCatharsis
@JCatharsis 2 жыл бұрын
It finally hit me I'm so high rn
@nikhileshkumar9126
@nikhileshkumar9126 2 жыл бұрын
don't do drugs bro. It's harmful.
@ncba
@ncba 2 жыл бұрын
Quite a common phrase
@dakshays6375
@dakshays6375 5 жыл бұрын
Damn !!! How did anyone come up with such an Algorithm
@nik220287
@nik220287 4 жыл бұрын
Man the way you explained it in the first 5 minutes just clarified everything. Thanks. Great video!
@user-bv6bi2sz8r
@user-bv6bi2sz8r 5 жыл бұрын
I was plagued by this problem for a very long time, you made it crystal clear, sir. Thank you!
@sshangrou8799
@sshangrou8799 6 жыл бұрын
thanks very much.it took me long time to think the algorithm on leetcode, your explanation is so clear and concise.Very nice
@maxfeldman6654
@maxfeldman6654 6 жыл бұрын
probably one of the best explanations i have seen so far, SUBSCRIBED!
@beer_bandhu
@beer_bandhu 5 жыл бұрын
This is amazing. I was so confused by this problem, you explained it so succinctly. Thanks
@arthamsreenivas8858
@arthamsreenivas8858 5 жыл бұрын
Tushar Sir, you literally saved my time with crystal clear explanation on this problem.
@abhijeetpatnaik5494
@abhijeetpatnaik5494 2 жыл бұрын
I can't stress enough, how clear this video explanation is. Really loving your work, and it's very very helpful.
@soulmusic6530
@soulmusic6530 3 жыл бұрын
after reading multiple explanations, this one finally made me understand how to think. Thanks for the video.
@sanjayizardar2263
@sanjayizardar2263 4 жыл бұрын
Perfectly explained... Found most useful among all the available videos on KZfaq for median in two sorted arrays.
@user-vb2rm9hl9d
@user-vb2rm9hl9d 5 жыл бұрын
this is the best explan I ve ever seen step by step with details, thank you
@marshallxu7480
@marshallxu7480 4 жыл бұрын
this is the best video of all time, it brings happiness. thank you!
@balajim7801
@balajim7801 4 жыл бұрын
Clear explanation. Thanks. A small error, 8:33 value of "end" should be 5 (size of small array). I followed just your example and coded, everything was right but failing always, until I watched your code & realized that end should have initial value of smallest array's length.
@eskuAdradit0
@eskuAdradit0 3 жыл бұрын
any clear explanation on why would we do it like this? is it the same reasoning behind adding + 1 to the sum of both arrays before dividing by two?
@haoyuwu894
@haoyuwu894 2 жыл бұрын
@@eskuAdradit0 I think it's because in some cases we can have all the elements in x on the left side. He mentioned that partitionX is "the number of elements partitioned to the left in x." So in those cases, partitionX can be the size of the small array. Consider this example: arrayX: [1, 2, 3, 4] and arrayY: [5, 6, 7, 8]. All the elements in x are smaller than elements in y. Hope this helps.
@DimpleSharma-jo9gf
@DimpleSharma-jo9gf 3 жыл бұрын
Such a great explanation! Love how you simplify things. Thanks a lot!!!
@rkalyankumar
@rkalyankumar 2 жыл бұрын
The best possible explanation of the problem I've seen so far. I have now clear idea on how median of two sorted array algorithm works using binary search & partitioning arrays. Good stuff!
@remixisthis
@remixisthis 5 жыл бұрын
Very well done detailed explanation. Much better than the LeetCode solution example. Thanks for taking the time to make this!
@yoosufahmadh3945
@yoosufahmadh3945 4 жыл бұрын
Repeat watching the first 6 minutes until you get it. Totally helps. Thank you so much. You simply put it
@zaheenrahman6608
@zaheenrahman6608 6 жыл бұрын
My boy Tushar Roy! Earned yourself a sub! Gonna help my algo course so much
@dongshuowu3454
@dongshuowu3454 5 жыл бұрын
Thank you for the wonderful video. I was stuck for a long time until you made it co clear to me.
@35sherminator
@35sherminator 5 жыл бұрын
Legendary. Very crisp and clear approach. Thank you very very much!
@pawandeepchor89
@pawandeepchor89 6 жыл бұрын
Excellent !! Nothing more one can do to explain this problem :) Thanks for sharing it buddy !! You are a star, keep up the good work, cheers !!
@bewareofnikhil
@bewareofnikhil Жыл бұрын
What a precise and correct explanation of the algorithm! Thanks for making and sharing this video, Tushar.
@JaySolanki91
@JaySolanki91 5 жыл бұрын
Simply Amazing !!! This algorithm was really helpful and you gave good examples to solve it. Especially the one in which you covered the corner cases.
@anondoggo
@anondoggo Жыл бұрын
Beautiful solution, thank you so much! I can't believe how close I was to the solution, I wished I pushed myself a bit harder, but this was a great educational experience. Thanks again!
@saurabhzalke4232
@saurabhzalke4232 3 жыл бұрын
So elegant and simple. One of the best tutorial ever! Keep it up.
@barmalini
@barmalini 5 жыл бұрын
I paused the video at 20:12 and now going to solve the problem at leetcode myself, thank you so much Tushar, your help for the rest of us who have never graduated from the CS but still want to become a sane programmer is invaluable
@kimmeng6939
@kimmeng6939 5 жыл бұрын
7:18 end should be 5 not 4 because we are searching which position we want to cut.
@prakashtiwari7834
@prakashtiwari7834 4 жыл бұрын
YES! Had the last element of first array been 10 instead of 15, the algorithm would've broken at 13:45. Anyways, the explanation was awesome.
@everydayleetcode2961
@everydayleetcode2961 4 жыл бұрын
@@prakashtiwari7834 I was wondering why did he take end as 4 and read this comment ! Thanks a lot !
@emilyhuang2759
@emilyhuang2759 3 жыл бұрын
But why not 4? The 5th index is empty....so I would think the end is 4...?
@sharmamukul938
@sharmamukul938 3 жыл бұрын
@@emilyhuang2759 Exactly even i'm not able to figure out why the end should be 5 and not 4 as it is clearly mentioned in the video that first array has 5 elements in total.
@varunwalia95
@varunwalia95 3 жыл бұрын
@@sharmamukul938 it should be the size of the array not index that is to be taken as high element according to code.
@hawaijarjs7496
@hawaijarjs7496 3 жыл бұрын
Thanks Bro for the excellent explanation! It is crystal clear now how the logic works for both odd/even scenarios. Appreciate your time. Cheers!
@dzungdev
@dzungdev 4 жыл бұрын
Thank you very much for your great explanation. I learn a lot from you, not only the code but the way to explain the problem.
@meganlee5897
@meganlee5897 4 жыл бұрын
Brilliant video and explanation! One minor change to the 1st example:initialization: 1) pick smaller len 2) start = 0, end = len, binary search the len of left size of X e.g with the first example: 1st round lo = 0, hi = 5, mid = lo + (hi - lo) / 2 = 2 2nd round lo = mid + 1 = 3, hi = 5
@gauravdudeja
@gauravdudeja 6 жыл бұрын
After watching 2 times it quite easy to understand. Keep up the good work Tushar.
@rogerwhite8061
@rogerwhite8061 5 жыл бұрын
Best explanation of this challenge I have found, thank you so much
@suvirsaurav5587
@suvirsaurav5587 4 жыл бұрын
In the first example, the end value at the start should be 5 as we can have a partition when all the 5 elements of array X will be on the left side.
@shaziasamreen8584
@shaziasamreen8584 3 жыл бұрын
Even after 5 years your video is best for this problem.Thank you so much for wonderful Explaination
@MohitSinha4
@MohitSinha4 4 жыл бұрын
Wow, your explanations are just great! Thank you so much!
@SonuSonu-tk5pk
@SonuSonu-tk5pk 6 жыл бұрын
very neat and excellent explanation
@tusharroy2525
@tusharroy2525 6 жыл бұрын
Thanks
@akshaysuman8168
@akshaysuman8168 6 жыл бұрын
Its so nice to see you back
@simingye7502
@simingye7502 4 жыл бұрын
Best explanation I have ever seen! Thank you!
@SourabhCA
@SourabhCA 4 жыл бұрын
Spent a lot of time trying to understand this from leetcode solutions and discussion. And you video explained it in 5 minutes
@Chandan-io3jm
@Chandan-io3jm 6 жыл бұрын
Best Channel for Data Structure && Algorithms !
@harishgovindan
@harishgovindan 4 жыл бұрын
Excellent video! Quite precise and covers all aspects! Thank you!
@ADITYAKUMAR-yd3ow
@ADITYAKUMAR-yd3ow 6 жыл бұрын
Perfect explanation, initially I though it would be difficult for me. But gradually you made me understand in only one go. Thanks 😀
@tusharroy2525
@tusharroy2525 6 жыл бұрын
Great.
@vladn.2332
@vladn.2332 6 жыл бұрын
Very clear and good explanation. Thank you very much, Tushar!
@dragonflyboss7162
@dragonflyboss7162 4 жыл бұрын
This explanation is so detailed, thank you!
@sanjitselvan5348
@sanjitselvan5348 Жыл бұрын
I went through 5 videos before landing here and finally understanding the intuition behind the solution. Thank you!
@mccloud35
@mccloud35 6 жыл бұрын
This explanation is fantastic. Great job Tushar!
@jessica_1811
@jessica_1811 11 ай бұрын
came to "like" this video only found out that I have "liked" this video 4 years ago when I was looking for my last job. Thank you Tushar.
@NeoMennon
@NeoMennon 5 жыл бұрын
Tushar you are awesome! I have watched few video about this question, yours is the most intuitive one
@Priyankachauhan-qv2rx
@Priyankachauhan-qv2rx 4 жыл бұрын
Hey Tushar, You make complicated problem look so simple and easy. Awesome job.
@video-vocabulary
@video-vocabulary 3 жыл бұрын
00:00 Introduction 01:39 Solution 06:19 Example 1 14:35 Example 2 20:11 Code
@abhinavgarg5611
@abhinavgarg5611 3 жыл бұрын
Thanks buddy😊
@jaatharsh
@jaatharsh 3 жыл бұрын
don't think there are words to express my gratitude towards your hard work in making such bloody awesome videos @TusharRoy your videos indeed are class apart & blessing for someone who wants to gain in-depth knowledge on DSA.
@CodingWithPrakash_
@CodingWithPrakash_ 3 жыл бұрын
kzfaq.info/get/bejne/jZOFlM-rvrypmYU.html
@umairalvi7382
@umairalvi7382 4 жыл бұрын
People like me wouldnt understand this video in one time,you gotta watch it multiple times ,read about the problem solving strategy then you will get the problem. He has explained in a very good manner
@lukaslehmann9708
@lukaslehmann9708 Жыл бұрын
Hi Sir, thanks for your great and detailed explanation...just had watched serveral videos and explanations before I saw your video...and finally I understood how it worked...It is really awsome that you used these examples to illustrate the problem (including the edge case) and in your code you also wrote so many annotations...I really appreciate your effort and great work.
@bharathik6479
@bharathik6479 4 жыл бұрын
Crystal clear explanation , Bro. You are helping a lot of people, Please Keep up the good Work.
@VishwajeetPandeyGV
@VishwajeetPandeyGV 5 жыл бұрын
Thanks for this. You made it very clear & easy & fast to understand
@krishna0908
@krishna0908 6 жыл бұрын
Excellent explanation, great clarity. Thanks Tushar.
@shwetankgupta
@shwetankgupta 5 жыл бұрын
Finally, I understood the crux of this problem. Thanks for the enlightenment.
@matthkang
@matthkang 5 жыл бұрын
Thank you for making it clear and easy to understand!
@priyanka.sarkar
@priyanka.sarkar 5 жыл бұрын
Hats off sir...I am really overwhelmed by the way you explained this algorithm and made it so easy and simple...(y) Thank you so much...:-)
@somiljain896
@somiljain896 6 күн бұрын
The best explaination with perfect testcases that I found for this question on Internet. Thank you!
@biswajeetchatterjee4721
@biswajeetchatterjee4721 5 жыл бұрын
Thanks Tushar.. Your videos really help to understand complex algos.. Keep it up and keep posting videos like this :)
@wengao6544
@wengao6544 11 ай бұрын
This video is definitely the most effective one in providing a clear explanation of the algorithm
@shashankshekharkaushik1567
@shashankshekharkaushik1567 2 жыл бұрын
I was so confuse how to solve this without taking care of corner cases as extra, your explanation was awesome. Thanks
@vinayybhore
@vinayybhore 6 жыл бұрын
Excellent Solution and the best so far explanation for this problem on youtube :)
@achyutaarjunneupane1154
@achyutaarjunneupane1154 6 жыл бұрын
great sir, got it in single explanation, I looked all over for over 4 hr
@tusharroy2525
@tusharroy2525 6 жыл бұрын
+achyut aarjunneupane nice
@vishnup3182
@vishnup3182 4 жыл бұрын
Best explanation found so far. Thanks !
@Destiny22377
@Destiny22377 4 жыл бұрын
Great solution. Not every detail was explained but as everyone else was saying this is probably the best solution on the net and if not it is one of the best ! The missing details can be inferred
@vishwajeetpawar5074
@vishwajeetpawar5074 2 жыл бұрын
Thanks Tushar.Your explanation helped a lot to understand the depth of logic and algorithm behind this question.
@jinny5025
@jinny5025 3 жыл бұрын
wow there's nothing more than clearer than this! thanks :) you just saved my time
@double_courage57
@double_courage57 3 жыл бұрын
@4:30 - I took a second to understand this : Think of the final sorted array (without duplicates) and draw a median line. We need to find the average of numbers which are immediately to the left and right of that median line. If x2 is immediately to the left of the median line, it has to be greater than y5 (remember final array is sorted). Similarly, if y6 is to the right of the median line it has to be lesser than x3. Hope this helps someone!
@TheBuzoTechie
@TheBuzoTechie 2 жыл бұрын
thanks for the extra intuition :)
@return1210
@return1210 Жыл бұрын
Thanks a lot!
@ahasunos5914
@ahasunos5914 2 жыл бұрын
Thank you so much Tushar. This explanation will last for generations.
@alejandrofarias7320
@alejandrofarias7320 5 жыл бұрын
Very good videos. You are great instructor. Cheers from México.
@techbarikcom
@techbarikcom 4 жыл бұрын
You are making my life a lot easier! May God bless you
@nandanimadhukar
@nandanimadhukar 3 жыл бұрын
Great explanation with ample examples! Keep up the good work
@stanleyakachukwu7881
@stanleyakachukwu7881 2 жыл бұрын
Brother, you have done well in explaining this. Thanks! I wanted to abandon this until I saw your video. With what I have known now I can go and write it myself until I pass it without looking at random solutions across the internet. I have subscribed for more.
@juliahamilton3493
@juliahamilton3493 4 жыл бұрын
Thank you so much for explaining the algorithm! Very clear!
@DonchenkoNadia
@DonchenkoNadia 3 жыл бұрын
Tushar, thank you so much! You explained it perfectly! If someone need solution in Python, here it is: class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1) > len(nums2): return self.findMedianSortedArrays(nums2, nums1); x = len(nums1) y = len(nums2) low = 0 high = x while low
@gunahawk6893
@gunahawk6893 Жыл бұрын
clean implementation good job
@jimz2392
@jimz2392 5 жыл бұрын
Thank you Tushar, your video helps me a lot!
@pi3ni0
@pi3ni0 2 жыл бұрын
Thanks, good explanation. I was looking for different resources, but it was the best so far :)
@PhoenixRisingFromAshes471
@PhoenixRisingFromAshes471 3 жыл бұрын
Jahapana tussi great .........sir i read a lot about this problem solution everywhere but finally came to understand from your video only...you made a very tricky concept so simple to understand
@vishnu_bhatt
@vishnu_bhatt 6 жыл бұрын
Helped a lot bro.Thank you for such good explanations.
@j50313j50313
@j50313j50313 4 жыл бұрын
You save my life. Just watch for 8 minutes and come up with a solution by myself!
@junjiechen7341
@junjiechen7341 6 жыл бұрын
Very down to earth explaination.
@jayachandrann6825
@jayachandrann6825 6 жыл бұрын
Perfect explanation, thanks for your hard work !!!...
@nabidulalam6956
@nabidulalam6956 3 жыл бұрын
Simple and elegant explanation. Hats off.
@rapetiraviteja3678
@rapetiraviteja3678 4 жыл бұрын
elegant explanation! thank you Tushar :D
@user-pw1th5et9b
@user-pw1th5et9b 2 жыл бұрын
Thank you so much. Your explanation is the best. Only with you I understood how to solve that problem.
@kumarann3483
@kumarann3483 5 жыл бұрын
clear explanation and concise code, good work!
@amirabdou4940
@amirabdou4940 3 жыл бұрын
Excellent walkthrough of the algo and the code. kudos bro
@user-hr1tx7bo1w
@user-hr1tx7bo1w 5 жыл бұрын
Thank you, it's very helpful.
@ehsona1827
@ehsona1827 4 жыл бұрын
the way the problem was broken down, amazing solution.
@igenyar
@igenyar 3 жыл бұрын
Your explanation is so sharp clear. Thanks!
@DhananjayTyagi24
@DhananjayTyagi24 4 жыл бұрын
The best explanation so far.
@sindhusp8935
@sindhusp8935 3 жыл бұрын
This is such a neat algo! thanks for the explanation
@kulkarnianiket929
@kulkarnianiket929 5 жыл бұрын
Great video! I think you need to divide by 2.0 on line 46. It failed when I ran it with input1 as [1,2] and input2 [3,4].
@britisundarmondal7297
@britisundarmondal7297 4 жыл бұрын
Thank you for the wonderful video. Easy explanation for such a complex problem.
@WS-lv4kk
@WS-lv4kk 5 жыл бұрын
For odd total array size, instead of adding 1 in the (x+y+1)/2 and taking the max of the left half, I think you can just do (x+y)/2 and take min of the right half.
@pavithranravichandiran6720
@pavithranravichandiran6720 Жыл бұрын
Great observation!
@subhodeepganguly2575
@subhodeepganguly2575 4 жыл бұрын
Very Nice Explanation. One of the best videos of Tushar
@sharatchandra9198
@sharatchandra9198 3 жыл бұрын
Most Beautiful explanation and solution. My deepest gratitude to all your videos.
Median of Two Sorted Arrays - Binary Search - Leetcode 4
22:22
Wait for the last one! 👀
00:28
Josh Horton
Рет қаралды 83 МЛН
Children deceived dad #comedy
00:19
yuzvikii_family
Рет қаралды 4,3 МЛН
System Design : Design messaging/chat service like Facebook Messenger or Whatsapp
29:16
Tushar Roy - Coding Made Simple
Рет қаралды 349 М.
Lowest Common Ancestor Binary Tree
11:08
Tushar Roy - Coding Made Simple
Рет қаралды 250 М.
Knuth-Morris-Pratt(KMP) Pattern Matching(Substring search)
12:50
Tushar Roy - Coding Made Simple
Рет қаралды 1,1 МЛН
System Design : Design a service like TinyUrl
24:10
Tushar Roy - Coding Made Simple
Рет қаралды 562 М.
How to: Work at Google - Example Coding/Engineering Interview
24:02
Life at Google
Рет қаралды 7 МЛН
Trie Data Structure
19:40
Tushar Roy - Coding Made Simple
Рет қаралды 409 М.
System design : Design Autocomplete or Typeahead Suggestions for Google search
19:42
Tushar Roy - Coding Made Simple
Рет қаралды 305 М.
Binary Search Algorithm - Computerphile
18:34
Computerphile
Рет қаралды 156 М.
Wait for the last one! 👀
00:28
Josh Horton
Рет қаралды 83 МЛН