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

แชร์
ฝัง
  • เผยแพร่เมื่อ 24 ธ.ค. 2024

ความคิดเห็น • 737

  • @shaziasamreen8584
    @shaziasamreen8584 3 ปีที่แล้ว +3

    Even after 5 years your video is best for this problem.Thank you so much for wonderful Explaination

    • @xendu-d9v
      @xendu-d9v 20 วันที่ผ่านมา

      7 years now, its fresh

  • @shrimatkapoor2200
    @shrimatkapoor2200 4 ปีที่แล้ว +245

    I love when he says "once it hits you" like some kind of drug or something

    • @PolkadOfficial
      @PolkadOfficial 3 ปีที่แล้ว +11

      @Kayden Khalil Lol, that is scam! fake accounts

    • @nishantkumar1149
      @nishantkumar1149 3 ปีที่แล้ว +14

      It's a better than a drug and the dopamine released on solving questions is sickkkk.

    • @JCatharsis
      @JCatharsis 3 ปีที่แล้ว +6

      It finally hit me I'm so high rn

    • @nikhileshkumar9126
      @nikhileshkumar9126 3 ปีที่แล้ว

      don't do drugs bro. It's harmful.

    • @ncba
      @ncba 2 ปีที่แล้ว

      Quite a common phrase

  • @meganlee5897
    @meganlee5897 4 ปีที่แล้ว +5

    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

  • @barmalini
    @barmalini 5 ปีที่แล้ว +49

    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

  • @nik220287
    @nik220287 5 ปีที่แล้ว +32

    Man the way you explained it in the first 5 minutes just clarified everything. Thanks. Great video!

  • @rushivt
    @rushivt 5 หลายเดือนก่อน +1

    I have seen many other videos for this problem, but yours is the one that made me follow every step clearly. Thank you!

  • @dakshays6375
    @dakshays6375 5 ปีที่แล้ว +98

    Damn !!! How did anyone come up with such an Algorithm

  • @程龙-b1w
    @程龙-b1w 5 ปีที่แล้ว +8

    I was plagued by this problem for a very long time, you made it crystal clear, sir. Thank you!

  • @uzdik.student
    @uzdik.student 4 ปีที่แล้ว +43

    00:00 Introduction
    01:39 Solution
    06:19 Example 1
    14:35 Example 2
    20:11 Code

  • @jessica_1811
    @jessica_1811 ปีที่แล้ว +1

    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.

  • @sanjitselvan5348
    @sanjitselvan5348 ปีที่แล้ว

    I went through 5 videos before landing here and finally understanding the intuition behind the solution. Thank you!

  • @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

  • @DonchenkoNadia
    @DonchenkoNadia 3 ปีที่แล้ว +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 2 ปีที่แล้ว

      clean implementation good job

  • @wengao6544
    @wengao6544 ปีที่แล้ว

    This video is definitely the most effective one in providing a clear explanation of the algorithm

  • @abhijeetpatnaik5494
    @abhijeetpatnaik5494 2 ปีที่แล้ว +2

    I can't stress enough, how clear this video explanation is. Really loving your work, and it's very very helpful.

  • @balajim7801
    @balajim7801 4 ปีที่แล้ว +49

    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 ปีที่แล้ว +1

      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 ปีที่แล้ว +5

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

  • @double_courage57
    @double_courage57 4 ปีที่แล้ว +12

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

  • @somiljain896
    @somiljain896 6 หลายเดือนก่อน

    The best explaination with perfect testcases that I found for this question on Internet.
    Thank you!

  • @marshallxu7480
    @marshallxu7480 4 ปีที่แล้ว +10

    this is the best video of all time, it brings happiness. thank you!

  • @kimmeng6939
    @kimmeng6939 5 ปีที่แล้ว +78

    7:18 end should be 5 not 4 because we are searching which position we want to cut.

    • @prakashtiwari7834
      @prakashtiwari7834 4 ปีที่แล้ว +2

      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 4 ปีที่แล้ว

      But why not 4? The 5th index is empty....so I would think the end is 4...?

    • @sharmamukul938
      @sharmamukul938 4 ปีที่แล้ว

      @@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 4 ปีที่แล้ว

      @@sharmamukul938 it should be the size of the array not index that is to be taken as high element according to code.

  • @GHT0310
    @GHT0310 13 วันที่ผ่านมา

    im first-year student from Vietnam, thank you a lot for this helpful video, appreciate

  • @beer_bandhu
    @beer_bandhu 6 ปีที่แล้ว +47

    This is amazing. I was so confused by this problem, you explained it so succinctly. Thanks

  • @gauravghosh6562
    @gauravghosh6562 ปีที่แล้ว

    this is the best channel for coding hand down

  • @Destiny22377
    @Destiny22377 5 ปีที่แล้ว

    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

  • @SourabhCA
    @SourabhCA 5 ปีที่แล้ว

    Spent a lot of time trying to understand this from leetcode solutions and discussion. And you video explained it in 5 minutes

  • @soulmusic6530
    @soulmusic6530 4 ปีที่แล้ว +3

    after reading multiple explanations, this one finally made me understand how to think.
    Thanks for the video.

  • @anondoggo
    @anondoggo 2 ปีที่แล้ว +2

    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!

  • @PhoenixRisingFromAshes471
    @PhoenixRisingFromAshes471 4 ปีที่แล้ว

    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

  • @ahasunos5914
    @ahasunos5914 3 ปีที่แล้ว

    Thank you so much Tushar. This explanation will last for generations.

  • @remixisthis
    @remixisthis 5 ปีที่แล้ว +4

    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

  • @rkalyankumar
    @rkalyankumar 3 ปีที่แล้ว

    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!

  • @suvirsaurav5587
    @suvirsaurav5587 5 ปีที่แล้ว +19

    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.

  • @sharatchandra9198
    @sharatchandra9198 4 ปีที่แล้ว

    Most Beautiful explanation and solution. My deepest gratitude to all your videos.

  • @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.

  • @maxfeldman6654
    @maxfeldman6654 6 ปีที่แล้ว +11

    probably one of the best explanations i have seen so far, SUBSCRIBED!

  • @sshangrou8799
    @sshangrou8799 7 ปีที่แล้ว +17

    thanks very much.it took me long time to think the algorithm on leetcode, your explanation is so clear and concise.Very nice

  • @bewareofnikhil
    @bewareofnikhil 2 ปีที่แล้ว +1

    What a precise and correct explanation of the algorithm! Thanks for making and sharing this video, Tushar.

  • @vikasaggarwal2834
    @vikasaggarwal2834 2 ปีที่แล้ว

    i usually don't comments on videos but your method of explaining made me comment on this...
    Superb video boss..

  • @saurabhzalke4232
    @saurabhzalke4232 4 ปีที่แล้ว +1

    So elegant and simple. One of the best tutorial ever! Keep it up.

  • @seekingWisdomAcrossWorlds
    @seekingWisdomAcrossWorlds 3 ปีที่แล้ว

    I was so confuse how to solve this without taking care of corner cases as extra, your explanation was awesome. Thanks

  • @MykolaDolgalov
    @MykolaDolgalov 4 ปีที่แล้ว +2

    *EDIT:* Thank you for the video. I watched it carefully, then coded the solution from memory. And then I compared to your solution, and mine is a little simpler and easier to understand (code is in the first comment). *Initial comment* 14:41 here it is obvious from the data that we must compare the rightmost and leftmost elements to see if the values in the arrays even overlap in range. If they don't we should skip the binary search and just treat them as one continuous sorted array, and find the median in it directly.
    Thank you for the wonderful videos.

    • @MykolaDolgalov
      @MykolaDolgalov 4 ปีที่แล้ว +1

      A somewhat simpler and easier to follow code:
      public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int len1 = nums1.length;
      int len2 = nums2.length;
      int res = 0;
      if(len2 < len1)
      return findMedianSortedArrays(nums2, nums1);
      int partitionX = len1 / 2;
      int low = 0;
      int high = len1;
      while(low 0 ? nums1[partitionX - 1] : Integer.MIN_VALUE;
      int num1R = partitionX < len1 ? nums1[partitionX] : Integer.MAX_VALUE;
      int num2L = partitionY > 0 ? nums2[partitionY - 1] : Integer.MIN_VALUE;
      int num2R = partitionY < len2 ? nums2[partitionY] : Integer.MAX_VALUE;
      if(num1L = num2L) { // found correct comb
      if((len1 + len2) % 2 != 0)
      return Math.max(num1L, num2L);
      else
      return 1.0*(Math.max(num1L, num2L) + Math.min(num1R, num2R)) / 2.0;
      } else if(num1R < num2L) { // need to move to the right
      low = ++partitionX;
      } else
      high = --partitionX;
      }
      return Double.MIN_VALUE;
      }

  • @himangshubiswas542
    @himangshubiswas542 ปีที่แล้ว

    Because of you I am going to solve this problem otherwise I thought I will skip it, thank you

  • @arthamsreenivas8858
    @arthamsreenivas8858 5 ปีที่แล้ว +1

    Tushar Sir, you literally saved my time with crystal clear explanation on this problem.

  • @jaatharsh
    @jaatharsh 4 ปีที่แล้ว

    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.

  • @subhodeepganguly2575
    @subhodeepganguly2575 4 ปีที่แล้ว

    Very Nice Explanation. One of the best videos of Tushar

  • @韓覲
    @韓覲 3 ปีที่แล้ว

    I can never figure it out without this video.

  • @ADITYAKUMAR-yd3ow
    @ADITYAKUMAR-yd3ow 7 ปีที่แล้ว +114

    Perfect explanation, initially I though it would be difficult for me. But gradually you made me understand in only one go.
    Thanks 😀

  • @ИванЕлисеев-р1з
    @ИванЕлисеев-р1з 3 ปีที่แล้ว

    Thank you so much. Your explanation is the best. Only with you I understood how to solve that problem.

  • @sanjayizardar2263
    @sanjayizardar2263 4 ปีที่แล้ว

    Perfectly explained... Found most useful among all the available videos on TH-cam for median in two sorted arrays.

  • @李克弱
    @李克弱 5 ปีที่แล้ว +1

    this is the best explan I ve ever seen
    step by step with details,
    thank you

  • @achyutaarjunneupane1154
    @achyutaarjunneupane1154 7 ปีที่แล้ว

    great sir, got it in single explanation, I looked all over for over 4 hr

  • @mukut5ul
    @mukut5ul 3 ปีที่แล้ว

    These videos are great equivalent to full computer science degree content

  • @rahul-patil
    @rahul-patil 5 ปีที่แล้ว +17

    15:24 If there are n element then we can partition that array in n+1 no. of ways.
    E.G 4 elements then we partition it in.
    1) 0 - 4
    2) 1 - 3
    3) 2 - 2
    4) 3 - 1
    5) 4 - 0

  • @Avinashkumar-xt4zq
    @Avinashkumar-xt4zq 3 ปีที่แล้ว

    Best explanation present on the Internet!

  • @_PRITIJHA
    @_PRITIJHA 4 ปีที่แล้ว

    Your channel solves all my doubt

  • @dzungdev
    @dzungdev 5 ปีที่แล้ว +1

    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.

  • @Chandan-io3jm
    @Chandan-io3jm 7 ปีที่แล้ว

    Best Channel for Data Structure && Algorithms !

  • @tvbuff
    @tvbuff 3 ปีที่แล้ว

    You truly are making coding simple !

  • @vishwajeetpawar5074
    @vishwajeetpawar5074 3 ปีที่แล้ว

    Thanks Tushar.Your explanation helped a lot to understand the depth of logic and algorithm behind this question.

  • @nabidulalam6956
    @nabidulalam6956 4 ปีที่แล้ว

    Simple and elegant explanation. Hats off.

  • @semurgx
    @semurgx 3 ปีที่แล้ว

    this one of the best explanation on youtube, awesome!

  • @siddharthkhandelwal933
    @siddharthkhandelwal933 ปีที่แล้ว

    Very well explained, the code is very clear and precise. Thanks

  • @pi3ni0
    @pi3ni0 2 ปีที่แล้ว +1

    Thanks, good explanation. I was looking for different resources, but it was the best so far :)

  • @niksmachnih264
    @niksmachnih264 2 ปีที่แล้ว

    The best explanation that I ever heard

  • @dongshuowu3454
    @dongshuowu3454 5 ปีที่แล้ว +1

    Thank you for the wonderful video. I was stuck for a long time until you made it co clear to me.

  • @techbarikcom
    @techbarikcom 4 ปีที่แล้ว

    You are making my life a lot easier! May God bless you

  • @j50313j50313
    @j50313j50313 4 ปีที่แล้ว

    You save my life.
    Just watch for 8 minutes and come up with a solution by myself!

  • @shashikantdivekar7839
    @shashikantdivekar7839 3 ปีที่แล้ว

    Very good explanation. Thank you Tushar Roy.

  • @bharathik6479
    @bharathik6479 4 ปีที่แล้ว

    Crystal clear explanation , Bro. You are helping a lot of people, Please Keep up the good Work.

  • @stratonov
    @stratonov 2 ปีที่แล้ว +1

    Beautiful lovely brilliantly handled edge cases

  • @കള്ള_ചക്കോ
    @കള്ള_ചക്കോ 4 ปีที่แล้ว +1

    give this man a medal

  • @shwetankgupta
    @shwetankgupta 5 ปีที่แล้ว +5

    Finally, I understood the crux of this problem. Thanks for the enlightenment.

  • @hawaijarjs7496
    @hawaijarjs7496 4 ปีที่แล้ว +1

    Thanks Bro for the excellent explanation! It is crystal clear now how the logic works for both odd/even scenarios. Appreciate your time. Cheers!

  • @pawandeepchor89
    @pawandeepchor89 6 ปีที่แล้ว +2

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

  • @lukaslehmann9708
    @lukaslehmann9708 2 ปีที่แล้ว

    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.

  • @DimpleSharma-jo9gf
    @DimpleSharma-jo9gf 4 ปีที่แล้ว +1

    Such a great explanation! Love how you simplify things. Thanks a lot!!!

  • @35sherminator
    @35sherminator 5 ปีที่แล้ว

    Legendary. Very crisp and clear approach. Thank you very very much!

  • @mrinmoypaul6810
    @mrinmoypaul6810 3 ปีที่แล้ว

    Tushar Sir tumi Bhogowan, Love from West Bengal

  • @DhananjayTyagi24
    @DhananjayTyagi24 5 ปีที่แล้ว

    The best explanation so far.

  • @qingyufan7416
    @qingyufan7416 4 ปีที่แล้ว

    Best explanation with examples. Thx a lot.

  • @neerajlajpal8858
    @neerajlajpal8858 4 ปีที่แล้ว

    Amazing video. Clear and concise explanation

  • @SonuSonu-tk5pk
    @SonuSonu-tk5pk 7 ปีที่แล้ว +17

    very neat and excellent explanation

  • @gauravdudeja
    @gauravdudeja 6 ปีที่แล้ว

    After watching 2 times it quite easy to understand. Keep up the good work Tushar.

  • @zaheenrahman6608
    @zaheenrahman6608 6 ปีที่แล้ว +5

    My boy Tushar Roy! Earned yourself a sub! Gonna help my algo course so much

  • @jinny5025
    @jinny5025 4 ปีที่แล้ว

    wow there's nothing more than clearer than this! thanks :) you just saved my time

  • @manojamrutharaj9071
    @manojamrutharaj9071 3 ปีที่แล้ว

    Thanks Tushar for the detailed explanation.

  • @JaySolanki91
    @JaySolanki91 6 ปีที่แล้ว +1

    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.

  • @kalashnikov203
    @kalashnikov203 4 ปีที่แล้ว

    The best explanation on this topic.

  • @priyankachauhan0112
    @priyankachauhan0112 5 ปีที่แล้ว

    Hey Tushar,
    You make complicated problem look so simple and easy. Awesome job.

  • @jacobstech1777
    @jacobstech1777 3 ปีที่แล้ว

    Simply the best explanation.

  • @nathan_milan_blacksmith3926
    @nathan_milan_blacksmith3926 4 ปีที่แล้ว

    clear thought and clear code. God bless u

  • @jatintayal4010
    @jatintayal4010 5 หลายเดือนก่อน

    Such an elegant explanation !!

  • @NeoMennon
    @NeoMennon 5 ปีที่แล้ว

    Tushar you are awesome! I have watched few video about this question, yours is the most intuitive one

  • @VishwajeetPandeyGV
    @VishwajeetPandeyGV 5 ปีที่แล้ว

    Thanks for this. You made it very clear & easy & fast to understand

  • @yu-nz8sj
    @yu-nz8sj 2 ปีที่แล้ว

    best explanation on the internet!!

  • @rogerwhite8061
    @rogerwhite8061 6 ปีที่แล้ว

    Best explanation of this challenge I have found, thank you so much

  • @igenyar
    @igenyar 3 ปีที่แล้ว

    Your explanation is so sharp clear. Thanks!

  • @ramizrizwan3057
    @ramizrizwan3057 ปีที่แล้ว

    such an incredibly good video. amazing explanation

  • @msteja
    @msteja 3 ปีที่แล้ว

    Geniusly explained the algo 🙏🏻👏🏻